Shorter arithmetization of nondeterministic computations
From MaRDI portal
Publication:496013
DOI10.1016/j.tcs.2015.07.030zbMath1430.68108OpenAlexW935592923MaRDI QIDQ496013
Zeyuan Allen Zhu, Alessandro Chiesa
Publication date: 16 September 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.030
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other nonclassical models of computation (68Q09) Classical models of computation (Turing machines, etc.) (68Q04)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial PCPs with short proofs
- Interactive proof systems and alternating time-space complexity
- Arithmetization: A new method in structural complexity theory
- On O(Tlog T) reduction from RAM computations to satisfiability
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Nearly-linear size holographic proofs
- SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
- Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Short Pairing-Based Non-interactive Zero-Knowledge Arguments
- Proof verification and the hardness of approximation problems
- Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
- Locally testable codes and PCPs of almost-linear length
- Two-query PCP with subconstant error
- Robust pcps of proximity, shorter pcps and applications to coding
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- A New Lower Bound for the Number of Switches in Rearrangeable Networks
- Satisfiability Is Quasilinear Complete in NQL
- Relations Among Complexity Measures
- Algebraic methods for interactive proof systems
- IP = PSPACE
- IP = SPACE
- Interactive proofs and the hardness of approximating cliques
- Network information flow
- Robust Characterizations of Polynomials with Applications to Program Testing
- Succinct Non-interactive Arguments via Linear Interactive Proofs
- Quadratic Span Programs and Succinct NIZKs without PCPs
- Combinatorial PCPs with Efficient Verifiers
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- On the concrete efficiency of probabilistically-checkable proofs
- A Permutation Network
- On a Class of Rearrangeable Switching Networks Part I: Control Algorithm
- 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
- Small PCPs with low query complexity
