NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES

DOI10.1142/S0129054105003819zbMath1101.68598MaRDI QIDQ5714674

N. V. Vinodchandran

Publication date: 15 December 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

derandomizationinteractive proof systemscomplexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Zero knowledge and circuit minimization

Cites Work

• Unnamed Item
• If NP has polynomial-size circuits, then MA=AM
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Derandomizing Arthur-Merlin games under uniform assumptions
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
• On pseudorandomness and resource-bounded measure
• Easiness assumptions and hardness tests: Trading time for zero error

This page was built for publication: NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES