Holographic Proofs and Derandomization

DOI10.1137/S0097539703438629MaRDI QIDQ5700569zbMATH OpenFDO

Authors Dieter Van Melkebeek, Rahul Santhanam

Publication date 28 October 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

derandomizationArthur-Merlin gamesholographic proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Derandomizing Arthur-Merlin games under uniform assumptions
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• scientific article; zbMATH DE number 2080255
• Can every randomized algorithm be derandomized?
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

Cited in

(5)

• On probabilistic space-bounded machines with multiple access to random tape
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Improved simulation of nondeterministic Turing machines
• Nearly-linear size holographic proofs
• Typically-correct derandomization for small time and space

This page was built for publication: Holographic Proofs and Derandomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5700569)