The study of property testing is concerned with algorithms that solve approximate decision problems, while only probing a small fraction of their inputs. More specifically, a tester for a property Pi receives query access to an object x and is required to determine whether x is in Pi or x is far from Pi, using as little as possible queries to x.
A fundamental question that arises in any computational model is to understand the power of proof systems within the model. Indeed, the P neq NP conjecture, which deals with the power of proofs in polynomial time computation, is arguably the most important open problem in the theory of computation. The focus of this thesis is on understanding the power and limitations of proof systems within the framework of property testing.
We study locally verifiable proofs of proximity (LVPP), which are probabilistic proofs systems wherein the verifier queries a sublinear number of bits of a statement and is only required to reject statements that are far from valid. In their most basic form, the verifier receives, in addition to query access to the statement, also free access to a proof of sublinear length; such proof systems are called Merlin-Arthur proofs of proximity (MAP) and can be viewed as the MA (i.e., ``randomized NP'') analogue of property testing.
Other notable forms of LVPPs include interactive proofs of proximity (IPP), in which the verifier is allowed to communicate with an omniscient prover (rather than obtain a static proof), and probabilistically checkable proofs of proximity (PCPP), in which the verifier is only allowed to make a small number of queries to both statement and proof (which is typically longer than the statement, in the case of PCPPs). These proofs systems can be viewed as the IP and PCP analogues of property testing.
In this thesis, we initiate the study of some types of LVPPs and continue the study of others. Our main contributions include:
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, February 2017.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.