A toolbox for barriers on interactive oracle proofs
From MaRDI portal
Publication:6169366
DOI10.1007/978-3-031-22318-1_16zbMATH Open1519.94035MaRDI QIDQ6169366FDOQ6169366
Authors: Gal Arnon, Amey Bhangale, Alessandro Chiesa, Eylon Yogev 
Publication date: 14 August 2023
Published in: Theory of Cryptography (Search for Journal in Brave)
Recommendations
Cites Work
- Proof verification and the hardness of approximation problems
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- The complexity of satisfiability problems
- On interactive proofs with a laconic prover
- A PCP theorem for interactive proofs and applications
- On the complexity of interactive proofs with bounded communication
- Efficient probabilistically checkable proofs and applications to approximations
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- The PCP theorem by gap amplification
- Constant-round interactive proofs for delegating computation
- Random Debaters and the Hardness of Approximating Stochastic Functions
- On the NP-hardness of MAX-Not-2
- Libra: succinct zero-knowledge proofs with optimal prover computation
- Interactive oracle proofs
- Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
- Title not available (Why is that?)
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Fast Reed-Solomon interactive oracle proofs of proximity
- Interactive oracle proofs with constant rate and query complexity
- Computational integrity with a public random string from quasi-linear PCPs
- Linear-time arguments with sublinear verification from tensor codes
- Barriers for succinct arguments in the random oracle model
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- Succinct interactive oracle proofs: applications and limitations
- Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
- A PCP characterization of AM
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
Cited In (6)
- Barriers for succinct arguments in the random oracle model
- On interactive oracle proofs for Boolean R1CS statements
- Interactive oracle proofs
- Interactive oracle proofs with constant rate and query complexity
- A PCP theorem for interactive proofs and applications
- Succinct interactive oracle proofs: applications and limitations
This page was built for publication: A toolbox for barriers on interactive oracle proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169366)
