Speaker: Arie Matsliah (CWI).

Location: CWI portacabins (Kruislaan 413c), downstairs seminar room (C001)

A 3-query PCPP verifier for a property P \subset {0, 1}^n is a randomized O(1)-time algorithm that distinguishes (whp) between inputs that belong to P and inputs that are far (in Hamming distance) from all members of P. In this respect, a verifier is similar to a property-tester. However, in contrast to a tester, the verifier may query an auxiliary proof of proximity.

The "proof length" of a PCPP system is the maximal length of the auxiliary proof that is queried by the verifier, and the "soundness function" s(d) is the minimal rejection probability of inputs that are d-far (in relative Hamming distance) from P, where the minimum is taken over all such d-far inputs and all possible proofs that may accompany them.

In this talk we will see that any 3-query PCPP-verifier obtaining the "best possible" soundness must query an exponentially long proof.

No prior knowledge of the topic will be assumed.