Probabilistic checking of proofs: a new characterization of NP

By Sanjeev Arora, Shmuel Safra. 1998

How researchers see this paper

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

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, background): “Prior work on verifying computation focused on narrow classes of computation [32, 51], relied on physical-security assumptions [41, 47], assumed uncorrelated failures [19, 20], or achieved good asymptotics [2, 28, 30, 31, 33, 38, 44] but impractical concrete performance [46, 50].”
Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “In practice however, because they rely on complex Probabilistically Checkable Proofs (PCPs) [17] or fully-homomorphic encryption (FHE) [24], the performance is unacceptable – verifying small instances would take hundreds to trillions of years (§5.”
Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “…of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems.2 The formal definition can be stated as follows, Theorem A.11 ((Arora & Safra, 1998; Arora et al., 1998)).”
Verifying computations with state (2013, background): “To briefly compare the performance of Zaatar and Pinocchio, Pinocchio has superior amortization behavior (see above) but higher proving and setup costs (and hence higher cross-over points), by constant factors.”
Making argument systems for outsourced computation practical (sometimes) (2012, background): “The potential of PCPs and efficient arguments to serve as a foundation for verified computations has long been known to theorists [8, 9, 11, 14, 20, 39, 48, 49, 55].”
Full Accounting for Verifiable Outsourcing (2017, background): “In probabilistic proofs—Interactive Proofs (IPs) [12, 49, 50, 58, 76], arguments [30, 52, 54, 62], SNARGs [48], SNARKs [26, 47], and PCPs [9, 10]—a prover efficiently convinces a verifier of a claim, in such a way that the verifier is highly likely to reject a false claim.”
On maximizing welfare when utility functions are subadditive (2006, background): “It is known [1] that for every > 0 there is an α > 0 such that it is NP-hard to distinguish between ”yes instances” in which a graph has an independent set of size αn and ”no instances” in which every independent set is of size at most αn.”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “A ZK system based on the PCP Theorem (ZK-PCP) [74, 85, 49, 75, 71] has three additional advantages that are essential for ongoing public trust in computational integrity.”
Robust pcps of proximity, shorter pcps and applications to coding (2004, methodology): “The celebrated PCP Theorem [2, 1] asserts that probing a constant number of bits su.ces, and it turned out that three bits su.ce for rejecting false assertions with probability almost 1/2 (cf. [21, 19]).”
Massive Quasi-Clique Detection (2002, result): “[4,5] together with results of Feige et al.”
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique (2004, background): “All recent results, on the other hand, use the PCP Theorem as a black-box and then use Parallel Repetition and Fourier analysis.”
Verifying Computations with Streaming Interactive Proofs (2011, unknown): “For the range ( 2 , 6 ) , in the ﬁrst round the prover reports the sub-vector [ 3 , 8 , 1 , 7 , 6 ] (shown highlighted).”
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008, methodology): “One major milestone on this path was the discovery of probabilistically checkable proofs (PCPs) (see [1, 2, 5, 10] and the references therein).”