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

zbMATH Keywords

derandomizationisolation lemmagraph reachabilitycircuit certificationunambiguous nondeterminism

Mathematics Subject Classification ID

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

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

(8)

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

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)