Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

Webpage for a paper by Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan


Abstract

We continue the study of the trade-off between the length of PCPs and their query complexity. In particular, we present PCPs of double-logarithmic query complexity while incurring only a quasi-polylogarithmic overhead (over the standard NP-proof) in the proof length.
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 Proximity. While the new construction uses many of the standard techniques in PCPs, it does differ from previous constructions in fundamental ways, and in particular does not use the ``parallelization'' step of Arora et al. The alternative approach may be of independent interest.
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 of almost-linear length.

Material available on-line

See follow-up work (by the same authors).


Back to either Oded Goldreich's homepage. or general list of papers.