Robust pcps of proximity, shorter pcps and applications to coding

By Eli Ben-Sasson, Oded Goldreich, P. Harsha, Madhu Sudan, Salil P. Vadhan. Symposium on the Theory of Computing, 2004

339 citations recorded by the source corpus.

We continue the study of the trade-off between the length of PCP sand their query complexity, establishing the following main results(which refer to proofs of satisfiability of circuits of size n): 1 We present PCPs of length exp(Õ(log log n)2)•n that can be verified by making o(log logn) Boolean queries.For every ε>0, we present PCPs of length exp(logε n)• n that can be verified by making a constant number of Boolean queries. In both cases, false assertions are rejected withconstant probability (which may be set to be arbitrarily close to 1). The multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi-polylogarithmic in the first case (ofquery complexity o(log logn)), and 2(log n)ε, for any ε>0, in the second case (of constant query complexity). In contrast, previous results required at least 2 √logn overhead in the length, even to get query complexity 2 √log n. Our techniques include the introduction of a new variant of PCPs that we call "Robust PCPs". These new PCPs facilitate proof composition, which is a central ingredient in construction of PCP systems. (A related notion and its composition properties were discovered independently by Dinur and Reingold. ) Our main technical contribution is a construction of a "length-efficient" Robust PCP. 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 mapping k information bits to code words of length κ1+ε, for any ε>0.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3de35f6343f299780b52b171431d77b939d4ebe9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Scalable, transparent, and post-quantum secure computational integrity (2018, background): “The RPT problem assumes a verifier is given oracle access to f , and to auxiliary information like a probabilistically checkable proof of proximity (PCPP) [25, 48] or an interactive oracle proof of proximity (IOPP) [22, 94, 15]; the verifier’s task is to distinguish with high probability and with a ”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, background): “If P is honest, then πi is linear, so P can use the homomorphism of Enc(·) to compute Enc(pk,πi(r)) from Enc(pk, r), without learning r.”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “The details of the queries and checks appear elsewhere [8, 16, 37, 53].”
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique (2004, neutral): “[9]).”
Introduction to Property Testing (2017, methodology): “46 • An alternative approach, pursued and advocated in [44], is to take advantage of the specific structure of the queries, “bundle” the answers together (into a constant number of bundles) and show that the “bundled” answers are “robust” in a sense that fits proximity testing.”
Verifying computations without reexecuting them (2015, background): “The proofs arising from the PCP theorem (despite asymptotic improvements [10, 20]) were so long and complicated that it would have taken thousands of years to generate and check them, and more storage bits than there are atoms in the universe.”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, positive): “Following a line of work on PCPs with short proofs [4, 81, 55, 44, 12, 9, 11, 10, 69], Ben-Sasson et al.”
Making argument systems for outsourced computation practical (sometimes) (2012, methodology): “Below we describe a linear PCP that is used by [8] as a building block; this linear PCP is also presented in [16, 45], and we borrow some of our notation from these three sources.”
Delegating computation: interactive proofs for muggles (2008, background): “See the full version for details and theorem statements.”
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008, background): “Since the PCPP system reads only O(1) bits of the proof, this new system does too.”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “Initial constructions required proofs of length poly(T ) but length has been reduced since then [49, 43, 24, 21] and state-of-the-art proofs are of quasi-linear length in T , i.”