IP = PSPACE
From MaRDI portal
Publication:4302793
DOI10.1145/146585.146609zbMath0799.68096OpenAlexW2293988196WikidataQ55952565 ScholiaQ55952565MaRDI QIDQ4302793
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.146609
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Borel complexity and Ramsey largeness of sets of oracles separating complexity classes, Practical sublinear proofs for R1CS from lattices, \(\mathrm{C}^\ast\)-algebras. Abstracts from the workshop held August 7--13, 2022, Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II, Unnamed Item, The power of adaptiveness and additional queries in random-self- reductions, 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, Succinct non-interactive arguments via linear interactive proofs, 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, Interactive Oracle Proofs, 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, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, A PCP theorem for interactive proofs and applications, Zero knowledge and circuit minimization, On testing monomials in multivariate polynomials, Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle, 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], On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, Unnamed Item, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, An analytic criterion for CSAT, Quantum multi-prover interactive proof systems with limited prior entanglement., Unnamed Item, The hunting of the SNARK, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, Unnamed Item, Unnamed Item, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, On the Power of Statistical Zero Knowledge, Unnamed Item, ON THE POWER OF QUANTUM TAMPER-PROOF DEVICES, EPiC: efficient privacy-preserving counting for MapReduce, Linear Logic Proof Games and Optimization, Parallel Repetition of Two-Prover One-Round Games: An Exposition, Pseudo-deterministic Proofs, ON HIGHER ARTHUR-MERLIN CLASSES, On the cutting edge of relativization: The resource bounded injury method, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Generalized Quantum Arthur--Merlin Games, Strong self-reducibility precludes strong immunity, On relationships between statistical zero-knowledge proofs, An introduction to randomized algorithms, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, Probabilistic verification of proofs in calculuses, The complexity of debate checking, Shorter arithmetization of nondeterministic computations, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, On the power of quantum, one round, two prover interactive proof systems, Locally random reductions: Improvements and applications, Interactive proof systems and alternating time-space complexity, The ideal membership problem and polynomial identity testing, Avoiding simplicity is complex, What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\), On Complete Problems, Relativizations and Logics for Complexity Classes, Unnamed Item, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Deterministically testing sparse polynomial identities of unbounded degree, A nonadaptive NC checker for permutation group intersection, Playing Savitch and Cooking Games, Approximate evaluations of characteristic polynomials of Boolean functions, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Rational Sumchecks, Verifying quantum computations at scale: A cryptographic leash on quantum devices, The Complexity of Zero Knowledge, Unnamed Item, Randomized proofs in arithmetic, An application of quantum finite automata to interactive proof systems, Efficient Probabilistically Checkable Debates, Randomness and Computation, Unnamed Item, Unnamed Item, Unnamed Item, Enumerations of the Kolmogorov function, Verification of quantum computation: an overview of existing approaches, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Verifiable Stream Computation and Arthur--Merlin Communication, Interactive proofs and a Shamir-like result for real number computations, Outsourcing computation: the minimal refereed mechanism, Constant-Round Interactive Proofs for Delegating Computation, High-rate codes with sublinear-time decoding, A combination of testability and decodability by tensor products, Clique is hard to approximate within \(n^{1-\epsilon}\), Distributed interactive proofs for the recognition of some geometric intersection graph classes, 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, The Connes embedding problem: A guided tour, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Reed-Muller Codes, PSPACE is provable by two provers in one round, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs, PSPACE has constant-round quantum interactive proof systems, One complexity theorist's view of quantum computing
