Pages that link to "Item:Q1106840"
From MaRDI portal
The following pages link to Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes (Q1106840):
Displaying 50 items.
- On the complexity of interactive proofs with bounded communication (Q293359) (← links)
- A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes (Q294649) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- A linear-time algorithm for the orbit problem over cyclic groups (Q303693) (← links)
- Zero-information protocols and unambiguity in Arthur-Merlin communication (Q343848) (← links)
- A short note on Merlin-Arthur protocols for subset sum (Q344519) (← links)
- Which languages have 4-round zero-knowledge proofs? (Q421047) (← links)
- The complexity of debate checking (Q493647) (← links)
- A framework for non-interactive instance-dependent commitment schemes (NIC) (Q500985) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- The relativized relationship between probabilistically checkable debate systems, IP and PSPACE (Q673812) (← links)
- The reachability problem for finite cellular automata (Q674292) (← links)
- If NP has polynomial-size circuits, then MA=AM (Q674343) (← links)
- Arithmetization: A new method in structural complexity theory (Q685721) (← links)
- Non-deterministic exponential time has two-prover interactive protocols (Q685724) (← links)
- On the expression complexity of equivalence and isomorphism of primitive positive formulas (Q692919) (← links)
- On the power of interaction (Q751809) (← links)
- Outsourcing computation: the minimal refereed mechanism (Q777972) (← links)
- Statistical zero-knowledge languages can be recognized in two rounds (Q808692) (← links)
- Pseudorandom bits for constant depth circuits (Q808707) (← links)
- Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority (Q809588) (← links)
- On the undecidability of probabilistic planning and related stochastic optimization problems (Q814465) (← links)
- Quantum information and the PCP theorem (Q835644) (← links)
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) (Q859979) (← links)
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- On the asymmetric complexity of the group-intersection problem (Q963437) (← links)
- Isomorphism and canonization of tournaments and hypertournaments (Q988566) (← links)
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- Elimination of parameters in the polynomial hierarchy (Q1285590) (← links)
- The alternation hierarchy for sublogarithmic space is infinite (Q1312177) (← links)
- PSPACE is provable by two provers in one round (Q1318475) (← links)
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029) (← links)
- Randomness in interactive proofs (Q1321030) (← links)
- Combinatorial techniques for universal hashing (Q1329163) (← links)
- Hardness vs randomness (Q1337458) (← links)
- On the power of multi-prover interactive protocols (Q1341733) (← links)
- More on BPP and the polynomial-time hierarchy (Q1351599) (← links)
- On the hardness of computing the permanent of random matrices (Q1355377) (← links)
- Counting quantifiers, successor relations, and logarithmic space (Q1362332) (← links)
- Solvable black-box group problems are low for PP (Q1390854) (← links)
- Inverting onto functions. (Q1426007) (← links)
- The counting complexity of group-definable languages (Q1575546) (← links)
- Interactive and probabilistic proof-checking (Q1577488) (← links)
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity (Q1604200) (← links)
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back (Q1698392) (← links)
- Randomized proofs in arithmetic (Q1807460) (← links)
- Proving properties of interactive proofs by a generalized counting technique (Q1825663) (← links)
