We study the class of languages, denoted by @math , which have @math -prover games where each prover just sends a bit, with completeness @math and soundness error @math . For the case that @math (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ( Computational Complexity'02 ) demonstrate that @math exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., @math ). We demonstrate that for the case that @math , 1-bit @math -prover games exhibit a significantly richer structure: + (Folklore) When @math , @math ; + When @math , @math ; + When @math , @math ; + For @math and sufficiently large @math , @math ; + For @math , @math . As such, 1-bit @math -prover games yield a natural "quantitative" approach to relating complexity classes such as @math , @math , @math , @math , and @math . We leave open the question of whether a more fine-grained hierarchy (between @math and @math ) can be established for the case when @math .
We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class AM. This gives a PCP characterization' of AM analogous to the PCP Theorem for NP. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for PSPACE; however, we suggest that the result for AM might be of particular significance for attempts to derandomize this class. To test this notion, we pose some Randomized Optimization Hypotheses' related to our stochastic CSPs that (in light of our result) would imply collapse results for AM. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that, if some language in NP is hard-on-average against circuits of size 2^ Omega(n) , then there exist hard-on-average optimization problems of a particularly elegant form. All our proofs use a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity, and demonstrate their versatility. We also use known results on randomness-efficient soundness- and hardness-amplification. In particular, we make essential use of the Impagliazzo-Wigderson generator; our analysis relies on a recent Chernoff-type theorem for expander walks.