Algebraic methods for interactive proof systems
From MaRDI portal
Publication:4302792
DOI10.1145/146585.146605zbMath0799.68097OpenAlexW2082647621WikidataQ55918490 ScholiaQ55918490MaRDI QIDQ4302792
Noam Nisan, Lance J. Fortnow, Howard J. Karloff, Carstent Lund
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/146585.146605
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
Unnamed Item ⋮ Constant-Round Interactive Proof Systems for AC0[2 and NC1] ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ HyperPlonk: Plonk with linear-time prover and high-degree custom gates ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ Proving knowledge of isogenies: a survey ⋮ Practical sublinear proofs for R1CS from lattices ⋮ Batch arguments for \textsf{NP} and more from standard bilinear group assumptions ⋮ The power of natural properties as oracles ⋮ Counting vampires: from univariate sumcheck to updatable ZK-SNARK ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Lattice-based succinct arguments for NP with polylogarithmic-time verification ⋮ Structural complexity of rational interactive proofs ⋮ Nova: recursive zero-knowledge arguments from folding schemes ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ Doubly efficient interactive proofs over infinite and non-commutative rings ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Unnamed Item ⋮ Algebraic reductions of knowledge ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Linear Logic Proof Games and Optimization ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ The Monomial Ideal Membership Problem and Polynomial Identity Testing ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ Verifying quantum computations at scale: A cryptographic leash on quantum devices ⋮ The Complexity of Zero Knowledge ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Enumerations of the Kolmogorov function ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ High-rate codes with sublinear-time decoding ⋮ A combination of testability and decodability by tensor products ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Sumcheck arguments and their applications ⋮ The power of adaptiveness and additional queries in random-self- reductions ⋮ Tight state-restoration soundness in the algebraic group model ⋮ Hausdorff dimension and oracle constructions ⋮ Quantum information and the PCP theorem ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Probabilistic proof systems — A survey ⋮ On the power of multi-prover interactive protocols ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Non-interactive batch arguments for NP from standard assumptions ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Geometric sets of low information content ⋮ Interactive Oracle Proofs ⋮ On the hardness of computing the permanent of random matrices ⋮ Fully parallelized multi-prover protocols for NEXP-time ⋮ Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs ⋮ Spatial Isolation Implies Zero Knowledge Even in a Quantum World ⋮ Some Results on Interactive Proofs for Real Computations ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ Parallel approximation of min-max problems ⋮ Efficient proof composition for verifiable computation ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ A PCP theorem for interactive proofs and applications ⋮ Gemini: elastic SNARKs for diverse environments ⋮ Succinct arguments in the quantum random oracle model ⋮ Refereed delegation of computation ⋮ An Algebraic Proof of the Real Number PCP Theorem ⋮ Secure commitment against a powerful adversary ⋮ On Emulating Interactive Proofs with Public Coins ⋮ On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Quantum multi-prover interactive proof systems with limited prior entanglement. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Generalized Quantum Arthur--Merlin Games ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ On relationships between statistical zero-knowledge proofs ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Probabilistic verification of proofs in calculuses ⋮ Shorter arithmetization of nondeterministic computations ⋮ The relativized relationship between probabilistically checkable debate systems, IP and PSPACE ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ On the power of quantum, one round, two prover interactive proof systems ⋮ Locally random reductions: Improvements and applications ⋮ Non-interactive proofs of proximity ⋮ New collapse consequences of NP having small circuits ⋮ Interactive proof systems and alternating time-space complexity ⋮ The ideal membership problem and polynomial identity testing ⋮ Avoiding simplicity is complex ⋮ How to Verify a Quantum Computation ⋮ Unnamed Item ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Competing provers yield improved Karp-Lipton collapse results
This page was built for publication: Algebraic methods for interactive proof systems
