Holographic Proofs and Derandomization
DOI10.1137/S0097539703438629zbMATH Open1086.68044MaRDI QIDQ5700569FDOQ5700569
Dieter Van Melkebeek, Rahul Santhanam
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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
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)
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)
