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.
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back (Q1698392) (← links)
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games (Q1762663) (← links)
- Randomized proofs in arithmetic (Q1807460) (← links)
- Proving properties of interactive proofs by a generalized counting technique (Q1825663) (← links)
- PSPACE has constant-round quantum interactive proof systems (Q1870552) (← links)
- On the complexity of approximating the VC dimension. (Q1872731) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- The complexity of approximating a nonlinear program (Q1906280) (← links)
- The complexity of local dimensions for constructible sets (Q1977150) (← links)
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity (Q1983326) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Placing conditional disclosure of secrets in the communication complexity universe (Q2035998) (← links)
- Which languages have 4-round fully black-box zero-knowledge arguments from one-way functions? (Q2055669) (← links)
- Distributed interactive proofs for the recognition of some geometric intersection graph classes (Q2097349) (← links)
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) (Q2120065) (← links)
- Polynomially ambiguous probabilistic automata on restricted languages (Q2121470) (← links)
- Time- and space-efficient arguments from groups of unknown order (Q2139631) (← links)
- A PCP theorem for interactive proofs and applications (Q2170038) (← links)
- On the probabilistic closure of the loose unambiguous hierarchy (Q2346573) (← links)
- Knottedness is in NP, modulo GRH (Q2445896) (← links)
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy (Q2456368) (← links)
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets (Q2489141) (← links)
- Lower bounds for non-black-box zero knowledge (Q2490264) (← links)
- Graph Isomorphism is in SPP (Q2495656) (← links)
- On zero error algorithms having oracle access to one query (Q2498984) (← links)
- How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge (Q2516524) (← links)
- Polynomial-time reducibilities and ``almost all'' oracle sets (Q2639849) (← links)
- Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs (Q2799089) (← links)
- From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back (Q2799090) (← links)
- The multiparty communication complexity of set disjointness (Q2817790) (← links)
- On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs (Q2827722) (← links)
- Multiple Usage of Random Bits in Finite Automata (Q2898066) (← links)
- Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas (Q3007625) (← links)
- Private Coins versus Public Coins in Zero-Knowledge Proof Systems (Q3408218) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- New Limits to Classical and Quantum Instance Compression (Q3449566) (← links)
- Characterizing polynomial complexity classes by reducibilities (Q3489449) (← links)
- Succinct NP Proofs from an Extractability Assumption (Q3507432) (← links)
- Arthur and Merlin as Oracles (Q3599130) (← links)
- (Q3787473) (← links)
- (Q4005200) (← links)
- A hierarchy that does not collapse : alternations in low level space (Q4365021) (← links)
- (Q4472503) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- Generalized Quantum Arthur--Merlin Games (Q4634057) (← links)
- A Hierarchy Theorem for Interactive Proofs of Proximity (Q4638092) (← links)
- New collapse consequences of NP having small circuits (Q4645178) (← links)
- On closure properties of bounded two-sided error complexity classes (Q4835865) (← links)
- Proofs of Proximity for Distribution Testing (Q4993323) (← links)
- Constant-Round Interactive Proofs for Delegating Computation (Q4997311) (← links)
