Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform dete...

Full description

Bibliographic Details
Main Authors: Doron, Dean, Pyne, Edward, Tell, Roei
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing 2024
Online Access:https://hdl.handle.net/1721.1/155721

Similar Items

Similar Items