Algebraic methods for interactive proof systems
From MaRDI portal
Cited in
(only showing first 100 items - show all)- An application of quantum finite automata to interactive proof systems
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- The complexity of the max word problem and the power of one-way interactive proof systems
- PSPACE is provable by two provers in one round
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- Randomness in interactive proofs
- The power of adaptiveness and additional queries in random-self- reductions
- On the power of multi-prover interactive protocols
- Probabilistically checkable proofs and their consequences for approximation algorithms
- Geometric sets of low information content
- On the hardness of computing the permanent of random matrices
- Fully parallelized multi-prover protocols for NEXP-time
- A tight relationship between generic oracles and type-2 complexity theory
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Interactive and probabilistic proof-checking
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Relativized worlds with an infinite hierarchy
- Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs
- Non-interactive proofs of proximity
- Competing provers yield improved Karp-Lipton collapse results
- Randomized proofs in arithmetic
- PSPACE has constant-round quantum interactive proof systems
- One complexity theorist's view of quantum computing
- A case of depth-3 identity testing, sparse factorization and duality
- On relationships between statistical zero-knowledge proofs
- Probabilistic verification of proofs in calculuses
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- Continuous verifiable delay functions
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
- Delegation with updatable unambiguous proofs and PPAD-hardness
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- TurboIKOS: improved non-interactive zero knowledge and post-quantum signatures
- Sumcheck arguments and their applications
- Tight state-restoration soundness in the algebraic group model
- Non-interactive batch arguments for NP from standard assumptions
- Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
- Efficient proof composition for verifiable computation
- A PCP theorem for interactive proofs and applications
- Gemini: elastic SNARKs for diverse environments
- Succinct arguments in the quantum random oracle model
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- Interactive proofs and a Shamir-like result for real number computations
- On the probabilistic closure of the loose unambiguous hierarchy
- Hausdorff dimension and oracle constructions
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- On the power of quantum, one round, two prover interactive proof systems
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
- A note on the circuit complexity of PP
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Rational sumchecks
- Interactive Coding for Interactive Proofs
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- Input-oblivious proof systems and a uniform complexity perspective on P/poly
- An Algebraic Proof of the Real Number PCP Theorem
- Efficient Probabilistically Checkable Debates
- Short locally testable codes and proofs
- Randomness and computation
- Almost transparent short proofs for \(\mathrm{NP}_{\mathbb R}\)
- scientific article; zbMATH DE number 412256 (Why is no real title available?)
- Interactive oracle proofs
- Some results on interactive proofs for real computations
- Parallel approximation of min-max problems
- Refereed delegation of computation
- How to Verify a Quantum Computation
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Generalized quantum Arthur-Merlin games
- A hierarchy theorem for interactive proofs of proximity
- New collapse consequences of NP having small circuits
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Short locally testable codes and proofs: a survey in two parts
- Shorter arithmetization of nondeterministic computations
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Local decoding and testing of polynomials over grids
- Constant-round interactive proofs for delegating computation
- Fast Reed-Solomon interactive oracle proofs of proximity
- An exponential separation between MA and AM proofs of proximity
- scientific article; zbMATH DE number 7378343 (Why is no real title available?)
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Round complexity versus randomness complexity in interactive proofs
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- Probabilistic proof systems -- a survey
- Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- Non-cooperative rational interactive proofs
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
- Secure commitment against a powerful adversary
- On Emulating Interactive Proofs with Public Coins
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- On the power of statistical zero knowledge
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 7250157 (Why is no real title available?)
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
This page was built for publication: Algebraic methods for interactive proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302792)
