PCPs for Arthur-Merlin games and communication protocols
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/60160 |
| _version_ | 1811073637472534528 |
|---|---|
| author | Drucker, Andrew Donald |
| author2 | Scott Aaronson. |
| author_facet | Scott Aaronson. Drucker, Andrew Donald |
| author_sort | Drucker, Andrew Donald |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T09:36:11Z |
| format | Thesis |
| id | mit-1721.1/60160 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:36:11Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/601602019-04-12T16:01:57Z PCPs for Arthur-Merlin games and communication protocols Probabilistically Checkable Proofs for Arthur-Merlin games and communication protocols Drucker, Andrew Donald Scott Aaronson. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Includes bibliographical references (p. 59-62). 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. by Andrew Donald Drucker. S.M. 2010-12-06T17:31:35Z 2010-12-06T17:31:35Z 2010 2010 Thesis http://hdl.handle.net/1721.1/60160 681751234 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 62 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Drucker, Andrew Donald PCPs for Arthur-Merlin games and communication protocols |
| title | PCPs for Arthur-Merlin games and communication protocols |
| title_full | PCPs for Arthur-Merlin games and communication protocols |
| title_fullStr | PCPs for Arthur-Merlin games and communication protocols |
| title_full_unstemmed | PCPs for Arthur-Merlin games and communication protocols |
| title_short | PCPs for Arthur-Merlin games and communication protocols |
| title_sort | pcps for arthur merlin games and communication protocols |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/60160 |
| work_keys_str_mv | AT druckerandrewdonald pcpsforarthurmerlingamesandcommunicationprotocols AT druckerandrewdonald probabilisticallycheckableproofsforarthurmerlingamesandcommunicationprotocols |