We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has a ... more >>>

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>