We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

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 >>>

We define tests of boolean functions which
distinguish between linear (or quadratic) polynomials, and functions
which are very far, in an appropriate sense, from these
polynomials. The tests have optimal or nearly optimal trade-offs
between soundness and the number of queries.

In particular, we show that functions with small ... more >>>