scientific article; zbMATH DE number 7250162
From MaRDI portal
Publication:5121910
DOI10.4230/LIPIcs.CCC.2018.22zbMath1441.68101MaRDI QIDQ5121910
Omer Reingold, Ron D. Rothblum, Guy N. Rothblum
Publication date: 22 September 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Communication complexity, information complexity (68Q11)
Related Items
Non-interactive batch arguments for NP from standard assumptions ⋮ Batch arguments for \textsf{NP} and more from standard bilinear group assumptions ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Constant-Round Interactive Proofs for Delegating Computation
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of interactive proofs with bounded communication
- Non-deterministic exponential time has two-prover interactive protocols
- NP is as easy as detecting unique solutions
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Modern cryptography, probabilistic proofs and pseudo-randomness
- On interactive proofs with a laconic prover
- Fast approximate probabilistically checkable proofs
- Partial tests, universal tests and decomposability
- Non-Interactive Proofs of Proximity
- Proof verification and the hardness of approximation problems
- Probabilistically Checkable Arguments
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Arguments of Proximity
- The Knowledge Complexity of Interactive Proof Systems
- 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
- Interactive proofs and the hardness of approximating cliques
- A Hierarchy Theorem for Interactive Proofs of Proximity
- Non-interactive delegation and batch NP verification from standard computational assumptions
- Zero-Knowledge Proofs of Proximity
- Proofs of Proximity for Distribution Testing
- Constant-round interactive proofs for delegating computation
- Interactive proofs of proximity
