Shorter arithmetization of nondeterministic computations
DOI10.1016/J.TCS.2015.07.030zbMATH Open1430.68108OpenAlexW935592923MaRDI QIDQ496013FDOQ496013
Authors: Alessandro Chiesa, Zeyuan Allen Zhu 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09) Classical models of computation (Turing machines, etc.) (68Q04)
Cites Work
- Snarks for C: verifying program executions succinctly and in zero knowledge
- Title not available (Why is that?)
- Combinatorial PCPs with short proofs
- Nearly-linear size holographic proofs
- 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
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Relations Among Complexity Measures
- Interactive proofs and the hardness of approximating cliques
- Network information flow
- Title not available (Why is that?)
- Combinatorial PCPs with Efficient Verifiers
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Robust Characterizations of Polynomials with Applications to Program Testing
- Title not available (Why is that?)
- Interactive proof systems and alternating time-space complexity
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Title not available (Why is that?)
- Satisfiability Is Quasilinear Complete in NQL
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Title not available (Why is that?)
- Short pairing-based non-interactive zero-knowledge arguments
- Arithmetization: A new method in structural complexity theory
- Title not available (Why is that?)
- The PCP theorem by gap amplification
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Two-query PCP with subconstant error
- Robust PSPs of proximity, shorter PSPs and applications to coding
- A New Lower Bound for the Number of Switches in Rearrangeable Networks
- IP = SPACE
- Title not available (Why is that?)
- Succinct non-interactive arguments via linear interactive proofs
- Quadratic span programs and succinct NIZKs without PCPs
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- On the concrete efficiency of probabilistically-checkable proofs
- A Permutation Network
- Title not available (Why is that?)
- On a Class of Rearrangeable Switching Networks Part I: Control Algorithm
- Small PCPs with low query complexity
- On O(Tlog T) reduction from RAM computations to satisfiability
Cited In (4)
Uses Software
This page was built for publication: Shorter arithmetization of nondeterministic computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496013)
