Thesis Defense: Robust PCPs of Proximity and Shorter PCPs
Speaker: Prahladh Harsha , MIT CSAIL
Date: July 27 2004
Time: 2:00PM to 3:00PM
Location: 32-124
Contact: Prahladh Harsha, prahladh@mit.edu
Relevant URL: Thesis Defense Announcement
Abstract:
Probabilistically Checkable Proofs (PCPs) provide a format of rewriting and verifying mathematical proofs that allow efficient probabilistic verification based on probing very few bits of the rewritten proof. The celebrated PCP Theorem asserts that probing a constant number of bits suffices (in fact just 3 bits suffice). A natural question that arises in the construction of PCPs is by how much does this rewritting blow up the original proof while retaining low query complexity.
We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results.
1. We present PCPs of length n*quasipolylogn that can be verified by making o(loglog n) Boolean queries.
2. For every \eps >0, we present PCPs of length n*exp((log n)^\eps) that can be verified by making a constant number of Boolean queries.
Our techniques include the introduction of a new variant of PCPs that we call Robust PCPs of proximity. These new PCPs facilitate proof composition, which is a central ingredient in construction of PCP systems. Our main technical contribution is a construction of a length-efficient Robust PCP of proxmity.
We also obtain analogous quantitative results for locally testable codes. In addition, we introduce a relaxed notion of locally decodable codes, and present such codes mapping k information bits to codewords of length k^(1+\eps), for any \eps>0.
Committee:
Madhu Sudan (advisor)
Shafi Goldwasser
Mike Sipser
See other events that are part of
See other events happening in July 2004
