Derandomizing isolation in space-bounded settings

DOI10.4230/LIPICS.CCC.2017.5zbMATH Open1440.68076MaRDI QIDQ5111135FDOQ5111135

Authors: Dieter Van Melkebeek, Gautam Prakriya 

Publication date: 26 May 2020

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?

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)

Cited In (8)

• Title not available (Why is that?)
• 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)