Fast approximate probabilistically checkable proofs
From MaRDI portal
Recommendations
Cites work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A sublinear bipartiteness tester for bounded degree graphs
- An Optimal Algorithm for Monte Carlo Estimation
- Designing programs that check their work
- Finite state verifiers I
- scientific article; zbMATH DE number 4191094 (Why is no real title available?)
- Improved efficient arguments. (Preliminary version)
- Interactive proof systems and alternating time-space complexity
- Interactive proofs and the hardness of approximating cliques
- Linear-time encodable and decodable error-correcting codes
- Lower bounds for sampling algorithms for estimating the average
- Many-valued logics and holographic proofs
- Nearly-linear size holographic proofs
- On the power of multi-prover interactive protocols
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Self-testing/correcting with applications to numerical problems
- Space-bounded probabilistic game automata
- Spot-checkers
- The complexity of satisfiability problems
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(26)- Efficient rational proofs with strong utility-gap guarantees
- Proofs of proximity for context-free languages and read-once branching programs
- Non-interactive proofs of proximity
- Fast approximate PCPs for multidimensional bin-packing problems
- Probabilistic verification of proofs in calculuses
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- Interactive proofs for social graphs
- Efficient Probabilistically Checkable Debates
- Proofs of proximity for context-free languages and read-once branching programs
- Arguments of proximity (extended abstract)
- A hierarchy theorem for interactive proofs of proximity
- Zero-knowledge proofs of proximity
- Proofs of proximity for distribution testing
- Constant-round interactive proofs for delegating computation
- An exponential separation between MA and AM proofs of proximity
- Verified approximation algorithms
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- On the concrete efficiency of probabilistically-checkable proofs
- Erasures versus errors in local decoding and property testing
- Distribution-free proofs of proximity
- Public coin interactive proofs for label-invariant distribution properties
- Hamming weight proofs of proximity with one-sided error
- Local proofs approaching the witness length
- Doubly sub-linear interactive proofs of proximity
This page was built for publication: Fast approximate probabilistically checkable proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1881217)
