PCPs for Arthur-Merlin games and communication protocols

[摘要] Probabilistically Checkable Proofs (PCPs) are an important class of proof systems that have played a key role in computational complexity theory. In this thesis we study the power of PCPs in two new settings: Arthur-Merlin games and communication protocols. In the first part of the thesis, we give 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 derandomnize 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), en there exist hard-on-average optimization problems of a particularly elegant form. In the second part of the thesis, we study PCPs in the setting of communication protocols. Using techniques inspired by Dinur;;s proof of the PCP Theorem. we show that functions f (X, y) with nondeterministic circuits of size i have -distributed PCP protocols;; of proof length O(poly(m)) in which each verifier looks at a constant number of proof positions. We show a complementary negative result: a distributed PCP protocol using a proof of length f, in which Alice and Bob look at k bits of the proof while exchanging t bits of communication, can be converted into a PCP-free randomized protocol with communication bounded by In both parts of the thesis, our proofs make use of a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity. and demonstrate their versatility. In our work on Arthur-Merlin games, 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.

[发布机构] Massachusetts Institute of Technology