Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Greg Kuperberg:

TR11-144 | 2nd November 2011
Greg Kuperberg, Shachar Lovett, Ron Peled

Probabilistic existence of rigid combinatorial structures

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>

ISSN 1433-8092 | Imprint