Non-deterministic exponential time has two-prover interactive protocols

DOI10.1007/BF01200056zbMath0774.68041OpenAlexW4256317935WikidataQ56700057 ScholiaQ56700057MaRDI QIDQ685724

László Babai, Carstent Lund, Lance J. Fortnow

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200056

zbMATH Keywords

interactive proof systems program verification verification scheme for multilinearity

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., In search of an easy witness: Exponential time vs. probabilistic polynomial time., Sumcheck arguments and their applications, Quantum de Finetti theorems under local measurements with applications, Algebraic testing and weight distributions of codes., The power of adaptiveness and additional queries in random-self- reductions, The random oracle hypothesis is false, Bounds on 2-query locally testable codes with affine tests, Model independent approach to probabilistic models, Quantum information and the PCP theorem, An information-theoretic treatment of random-self-reducibility, Probabilistic proof systems — A survey, Interactive Proofs with Approximately Commuting Provers, On the power of multi-prover interactive protocols, Probabilistically checkable proofs and their consequences for approximation algorithms, A Hierarchy Theorem for Interactive Proofs of Proximity, Recent results in hardness of approximation, Time hierarchies for cryptographic function inversion with advice, Structural complexity theory: Recent surprises, A self-tester for linear functions over the integers with an elementary proof of correctness, On proving that a graph has no large clique: A connection with Ramsey theory, Interactive Oracle Proofs, Fully parallelized multi-prover protocols for NEXP-time, The hardness of approximate optima in lattices, codes, and systems of linear equations, Quantum Bilinear Optimization, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, RECYCLING RANDOM BITS IN PARALLEL, The complexity of approximating a nonlinear program, Local Expansion of Symmetrical Graphs, Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs, Average-case intractability vs. worst-case intractability, Robust simulations and significant separations, Simulating BPP using a general weak random source, Low-degree test with polynomially small error, Nonlocal Games with Noisy Maximally Entangled States are Decidable, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Model-checking hierarchical structures, Quantum multi-prover interactive proof systems with limited prior entanglement., Unnamed Item, 2-transitivity is insufficient for local testability, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), On derandomizing Yao's weak-to-strong OWF construction, PCP characterizations of NP: toward a polynomially-small error-probability, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Program result checking: A new approach to making programs more reliable, Fault-tolerance and complexity (Extended abstract), Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Combinatorial PCPs with efficient verifiers, Probabilistic verification of proofs in calculuses, The complexity of debate checking, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, On the power of quantum, one round, two prover interactive proof systems, Locally random reductions: Improvements and applications, New collapse consequences of NP having small circuits, Improved approximation algorithms for projection games, Symmetric LDPC codes and local testing, Arithmetization: A new method in structural complexity theory, Non-deterministic exponential time has two-prover interactive protocols, On being incoherent without being very hard, Constant-space quantum interactive proofs against multiple provers, Avoiding simplicity is complex, Unnamed Item, Fast approximate PCPs for multidimensional bin-packing problems, Parallelization of entanglement-resistant multi-prover interactive proofs, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Invariance in Property Testing, Testing Linear-Invariant Non-linear Properties: A Short Report, Optimal Testing of Reed-Muller Codes, Symmetric LDPC Codes and Local Testing, Testing low-degree polynomials over prime fields, Unnamed Item, Unnamed Item, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Three-Player Entangled XOR Games are NP-Hard to Approximate, Efficient Probabilistically Checkable Debates, Short Locally Testable Codes and Proofs, Almost Transparent Short Proofs for NPℝ, Unnamed Item, Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate, Quantum XOR Games, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, A unified framework for testing linear‐invariant properties, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Spot-checkers, Interactive and probabilistic proof-checking, Clique is hard to approximate within \(n^{1-\epsilon}\), On Dinur’s proof of the PCP theorem, What can be efficiently reduced to the Kolmogorov-random strings?, Uniform generation of NP-witnesses using an NP-oracle, Unnamed Item, The complexity of the max word problem and the power of one-way interactive proof systems, On the probabilistic closure of the loose unambiguous hierarchy, Self-testing/correcting with applications to numerical problems, Randomness vs time: Derandomization under a uniform assumption, 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, Succinct classical verification of quantum computation, The power of natural properties as oracles, \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem, \(\mathrm{C}^\ast\)-algebras. Abstracts from the workshop held August 7--13, 2022, Structural complexity of rational interactive proofs, Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II, Doubly efficient interactive proofs over infinite and non-commutative rings, On Active and Passive Testing, Parallel Repetition of Two-Prover One-Round Games: An Exposition, ON HIGHER ARTHUR-MERLIN CLASSES, On the computational complexity of bridgecard, The Complexity of Zero Knowledge, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, High-rate codes with sublinear-time decoding, A combination of testability and decodability by tensor products, Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity, The Connes embedding problem: A guided tour

Cites Work