Shorter arithmetization of nondeterministic computations
From MaRDI portal
(Redirected from Publication:496013)
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 4101157 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 3557235 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- scientific article; zbMATH DE number 1559566 (Why is no real title available?)
- scientific article; zbMATH DE number 3225079 (Why is no real title available?)
- scientific article; zbMATH DE number 3329939 (Why is no real title available?)
- scientific article; zbMATH DE number 967590 (Why is no real title available?)
- A New Lower Bound for the Number of Switches in Rearrangeable Networks
- A Permutation Network
- Algebraic methods for interactive proof systems
- Arithmetization: A new method in structural complexity theory
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Combinatorial PCPs with Efficient Verifiers
- Combinatorial PCPs with short proofs
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- IP = PSPACE
- IP = SPACE
- Interactive proof systems and alternating time-space complexity
- Interactive proofs and the hardness of approximating cliques
- Locally testable codes and PCPs of almost-linear length
- Nearly-linear size holographic proofs
- Network information flow
- On O(Tlog T) reduction from RAM computations to satisfiability
- On a Class of Rearrangeable Switching Networks Part I: Control Algorithm
- On the concrete efficiency of probabilistically-checkable proofs
- Probabilistic checking of proofs
- Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments
- Proof verification and the hardness of approximation problems
- Quadratic span programs and succinct NIZKs without PCPs
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Relations Among Complexity Measures
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Satisfiability Is Quasilinear Complete in NQL
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Short PCPs with Polylog Query Complexity
- Short pairing-based non-interactive zero-knowledge arguments
- Small PCPs with low query complexity
- Snarks for C: verifying program executions succinctly and in zero knowledge
- Succinct non-interactive arguments via linear interactive proofs
- The PCP theorem by gap amplification
- Two-query PCP with subconstant error
Cited in
(4)
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)
