Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with L vs. BPL:
TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

TR22-121 | 27th August 2022
William Hoza

Recent Progress on Derandomizing Space-Bounded Computation

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

ISSN 1433-8092 | Imprint