Holographic Proofs and Derandomization
From MaRDI portal
Publication:5700569
DOI10.1137/S0097539703438629zbMath1086.68044MaRDI QIDQ5700569
Dieter van Melkebeek, Rahul Santhanam
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
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
