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)

Full work available at URL https://doi.org/10.1137/S0097539703438629

zbMATH Keywords

Arthur-Merlin gamesderandomizationholographic proofs

Mathematics Subject Classification ID

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

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)

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

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)