Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
From MaRDI portal
Publication:1106840
DOI10.1016/0022-0000(88)90028-1zbMATH Open0652.03029DBLPjournals/jcss/BabaiM88OpenAlexW2148957455WikidataQ56386804 ScholiaQ56386804MaRDI QIDQ1106840FDOQ1106840
Authors: Shlomo Moran, László Babai 
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90028-1
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Universal classes of hash functions
- The complexity of theorem-proving procedures
- Riemann's hypothesis and tests for primality
- Alternation
- The knowledge complexity of interactive proof-systems
- A Fast Monte-Carlo Test for Primality
- Generating quasi-random sequences from semi-random sources
- The polynomial-time hierarchy
- Computational Complexity of Probabilistic Turing Machines
- BPP and the polynomial hierarchy
- Does co-NP have short interactive proofs ?
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Superconcentrators
- Title not available (Why is that?)
- Explicit constructions of linear-sized superconcentrators
- Title not available (Why is that?)
- A Note on Randomized Polynomial Time
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On Suborderings of Degrees of Recursive Unsolvability
- Title not available (Why is that?)
- Theory and practice of combinatorics. A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
- Bounded Round Interactive Proofs in Finite Groups
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Playing Savitch and cooking games
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Isomorphism and canonization of tournaments and hypertournaments
- Randomness in interactive proofs
- On the power of multi-prover interactive protocols
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Knottedness is in NP, modulo GRH
- Arithmetization: A new method in structural complexity theory
- Interactive and probabilistic proof-checking
- Derandomizing Arthur-Merlin games under uniform assumptions
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- On Dinur’s proof of the PCP theorem
- On the undecidability of probabilistic planning and related stochastic optimization problems
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Geometry and Combinatorics via Right-Angled Artin Groups
- A hierarchy that does not collapse : alternations in low level space
- Counting quantifiers, successor relations, and logarithmic space
- Derandomizing Arthur-Merlin games using hitting sets
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Hardness vs randomness
- Non-deterministic exponential time has two-prover interactive protocols
- On the complexity of interactive proofs with bounded communication
- A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
- Arthur and Merlin as Oracles
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- A linear-time algorithm for the orbit problem over cyclic groups
- Pseudorandom bits for constant depth circuits
- On the complexity of approximating the VC dimension.
- PSPACE has constant-round quantum interactive proof systems
- New collapse consequences of NP having small circuits
- The counting complexity of group-definable languages
- Statistical zero-knowledge languages can be recognized in two rounds
- Private coins versus public coins in zero-knowledge proof systems
- The complexity of local dimensions for constructible sets
- Approximate counting in bounded arithmetic
- The complexity of approximating a nonlinear program
- On the power of interaction
- The alternation hierarchy for sublogarithmic space is infinite
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- On the hardness of computing the permanent of random matrices
- Fault-tolerance and complexity (extended abstract)
- Succinct NP Proofs from an Extractability Assumption
- Lower bounds for non-black-box zero knowledge
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- A short note on Merlin-Arthur protocols for subset sum
- New limits to classical and quantum instance compression
- More on BPP and the polynomial-time hierarchy
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Outsourcing computation: the minimal refereed mechanism
- Quantum information and the PCP theorem
- PSPACE is provable by two provers in one round
- Title not available (Why is that?)
- A PCP theorem for interactive proofs and applications
- Arthur and Merlin as oracles
- The complexity of debate checking
- If NP has polynomial-size circuits, then MA=AM
- Solvable black-box group problems are low for PP
- How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge
- Inverting onto functions.
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Combinatorial techniques for universal hashing
- A framework for non-interactive instance-dependent commitment schemes (NIC)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Multiple usage of random bits in finite automata
- Which languages have 4-round zero-knowledge proofs?
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back
- Graph Isomorphism is in SPP
- Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority
- Randomized proofs in arithmetic
- The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
- The reachability problem for finite cellular automata
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Title not available (Why is that?)
- The complexity of generating test instances
- On the asymmetric complexity of the group-intersection problem
- On Emulating Interactive Proofs with Public Coins
- Randomization, persuasiveness and rigor in proofs
- Structural complexity of rational interactive proofs
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Time- and space-efficient arguments from groups of unknown order
- Characterizing polynomial complexity classes by reducibilities
- Complexity limitations on one-turn quantum refereed games
- On closure properties of bounded two-sided error complexity classes
- On the probabilistic closure of the loose unambiguous hierarchy
- Title not available (Why is that?)
- Elimination of parameters in the polynomial hierarchy
- The Complexity of Zero Knowledge
- A hierarchy theorem for interactive proofs of proximity
- Polynomial-time reducibilities and ``almost all oracle sets
- How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge
- HyperPlonk: Plonk with linear-time prover and high-degree custom gates
- Explainable arguments
- ON HIGHER ARTHUR-MERLIN CLASSES
- Placing conditional disclosure of secrets in the communication complexity universe
This page was built for publication: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106840)
