Derandomizing isolation in space-bounded settings

DOI10.4230/LIPICS.CCC.2017.5MaRDI QIDQ5111135zbMATH OpenFDO

Authors Dieter Van Melkebeek, Gautam Prakriya

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.5

zbMATH Keywords

circuit certificationderandomizationgraph reachabilityisolation lemmaunambiguous nondeterminism

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Derandomizing isolation in space-bounded settings
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• scientific article; zbMATH DE number 2019636
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Is Valiant-Vazirani's isolation probability improvable?

Cited in

(9)

• Is Valiant-Vazirani's isolation probability improvable?
• scientific article; zbMATH DE number 2019636 (Why is no real title available?)
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• Compressed Decision Problems in Hyperbolic Groups.
• Typically-correct derandomization for small time and space
• Derandomizing isolation in space-bounded settings
• Reproducibility and pseudo-determinism in log-space
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• Reachability in graphs with polynomially many surface non-separating cycles is in UL

This page was built for publication: Derandomizing isolation in space-bounded settings

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