A PCP theorem for interactive proofs and applications
From MaRDI portal
Publication:2170038
DOI10.1007/978-3-031-07085-3_3zbMath1497.68207OpenAlexW3208320247MaRDI QIDQ2170038
Eylon Yogev, Alessandro Chiesa, Gal Arnon
Publication date: 30 August 2022
Full work available at URL: https://doi.org/10.1007/978-3-031-07085-3_3
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Communication complexity, information complexity (68Q11)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- APPSSAT: Approximate probabilistic planning using stochastic satisfiability
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Randomness in interactive proofs
- Marlin
- On interactive proofs with a laconic prover
- Prover-efficient commit-and-prove zero-knowledge snarks
- Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
- Marlin: preprocessing zkSNARKs with universal and updatable SRS
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- Linear-time arguments with sublinear verification from tensor codes
- Succinct arguments in the quantum random oracle model
- Linear-size constant-query IOPs for delegating computation
- Aurora: transparent succinct arguments for R1CS
- Scalable zero knowledge with no trusted setup
- On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
- A PCP Characterization of AM
- Efficient Probabilistically Checkable Debates
- Proof verification and the hardness of approximation problems
- Interactive Oracle Proofs
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Short PCPs with Polylog Query Complexity
- The Knowledge Complexity of Interactive Proof Systems
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Random Debaters and the Hardness of Approximating Stochastic Functions
- Interactive proofs and the hardness of approximating cliques
- Computationally Sound Proofs
- Fast Reed-Solomon Interactive Oracle Proofs of Proximity
- Fiat-Shamir: from practice to theory
- Constant-round interactive proofs for delegating computation
- Fine-Tuning Groth-Sahai Proofs
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
- Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
- Stochastic Boolean satisfiability
