Fast approximate probabilistically checkable proofs
From MaRDI portal
Publication:1881217
DOI10.1016/j.ic.2003.09.005zbMath1075.68032OpenAlexW2061662395MaRDI QIDQ1881217
Ronitt Rubinfeld, Ravi Kumar, Funda Ergün
Publication date: 4 October 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2003.09.005
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (16)
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Arguments of Proximity ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Erasures versus errors in local decoding and property testing ⋮ Zero-Knowledge Proofs of Proximity ⋮ Proofs of Proximity for Distribution Testing ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Fast approximate PCPs for multidimensional bin-packing problems ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ \textsc{Fractal}: post-quantum and transparent recursive proofs from holography ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Interactive proofs for social graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for sampling algorithms for estimating the average
- Interactive proof systems and alternating time-space complexity
- Self-testing/correcting with applications to numerical problems
- On the power of multi-prover interactive protocols
- Spot-checkers
- A sublinear bipartiteness tester for bounded degree graphs
- Nearly-linear size holographic proofs
- Linear-time encodable and decodable error-correcting codes
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Probabilistic checking of proofs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Finite state verifiers I
- Space-bounded probabilistic game automata
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Designing programs that check their work
- Interactive proofs and the hardness of approximating cliques
- Robust Characterizations of Polynomials with Applications to Program Testing
- An Optimal Algorithm for Monte Carlo Estimation
- The complexity of satisfiability problems
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Property testing in bounded degree graphs
This page was built for publication: Fast approximate probabilistically checkable proofs
