Robust PCPs of Proximity, Shorter PCPs
and Applications to Coding
Webpage for a paper by Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan
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).
either Oded Goldreich's homepage.
or general list of papers.