Fast approximate probabilistically checkable proofs
From MaRDI portal
Publication:1881217
DOI10.1016/j.ic.2003.09.005zbMath1075.68032MaRDI QIDQ1881217
Ravi Kumar, Ronitt Rubinfeld, 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
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q60: Specification and verification (program logics, model checking, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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
