IP = PSPACE
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
- An introduction to randomized algorithms
- PSPACE is provable by two provers in one round
- BPP has subexponential time simulations unless EXPTIME has publishable 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
- A tight relationship between generic oracles and type-2 complexity theory
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- The hunting of the SNARK
- Randomized proofs in arithmetic
- PSPACE has constant-round quantum interactive proof systems
- One complexity theorist's view of quantum computing
- On relationships between statistical zero-knowledge proofs
- Probabilistic verification of proofs in calculuses
- What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Succinct non-interactive arguments via linear interactive proofs
- Non-interactive batch arguments for NP from standard assumptions
- Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
- A PCP theorem for interactive proofs and applications
- EPiC: efficient privacy-preserving counting for MapReduce
- Verification of quantum computation: an overview of existing approaches
- Interactive proofs and a Shamir-like result for real number computations
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On the probabilistic closure of the loose unambiguous hierarchy
- Hausdorff dimension and oracle constructions
- Zero knowledge and circuit minimization
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- On the power of quantum, one round, two prover interactive proof systems
- Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Rational sumchecks
- Input-oblivious proof systems and a uniform complexity perspective on P/poly
- IP = PSPACE using error-correcting codes
- \(\mathrm{QIP} = \mathrm{PSPACE}\)
- Finite state verifiers with constant randomness
- Efficient Probabilistically Checkable Debates
- Randomness and computation
- scientific article; zbMATH DE number 998060 (Why is no real title available?)
- Interactive oracle proofs
- Some results on interactive proofs for real computations
- ON THE POWER OF QUANTUM TAMPER-PROOF DEVICES
- Parallel approximation of min-max problems
- On complete problems, relativizations and logics for complexity classes
- On testing monomials in multivariate polynomials
- scientific article; zbMATH DE number 66620 (Why is no real title available?)
- An analytic criterion for CSAT
- IP = SPACE
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- On the cutting edge of relativization: the resource bounded injury method
- Generalized quantum Arthur-Merlin games
- A hierarchy theorem for interactive proofs of proximity
- scientific article; zbMATH DE number 4768 (Why is no real title available?)
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Strong self-reducibility precludes strong immunity
- The complexity of debate checking
- Shorter arithmetization of nondeterministic computations
- Pseudo-deterministic proofs
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Constant-round interactive proofs for delegating computation
- Fast Reed-Solomon interactive oracle proofs of proximity
- scientific article; zbMATH DE number 7378343 (Why is no real title available?)
- scientific article; zbMATH DE number 7378390 (Why is no real title available?)
- Round complexity versus randomness complexity in interactive proofs
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- Probabilistic proof systems -- a survey
- Non-cooperative rational interactive proofs
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Nonlocal Games with Noisy Maximally Entangled States are Decidable
- On Emulating Interactive Proofs with Public Coins
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Relativization and interactive proof systems in parameterized complexity theory
- On the power of statistical zero knowledge
- scientific article; zbMATH DE number 7250157 (Why is no real title available?)
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- Parallel repetition of two-prover one-round games: an exposition
- Playing Savitch and cooking games
- Verifying quantum computations at scale: a cryptographic leash on quantum devices
- Verifiable stream computation and Arthur-Merlin communication
- A combination of testability and decodability by tensor products
- QIP = PSPACE
- The Complexity of Zero Knowledge
- Enumerations of the Kolmogorov function
- High-rate codes with sublinear-time decoding
- Linear Logic Proof Games and Optimization
- ON HIGHER ARTHUR-MERLIN CLASSES
- The Connes embedding problem: a guided tour
- Reed-Muller Codes
- scientific article; zbMATH DE number 7650137 (Why is no real title available?)
- A nonadaptive NC checker for permutation group intersection
- Approximate evaluations of characteristic polynomials of Boolean functions
- scientific article; zbMATH DE number 7758324 (Why is no real title available?)
- Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
- Practical sublinear proofs for R1CS from lattices
This page was built for publication: IP = PSPACE
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302793)
