Prof. Dean Doron
Know all about my research
Nearly Optimal Pseudorandomness from Hardness
Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown.
| Publication language | English |
| Journal | Journal of the ACM |
| Volume | 69 |
| Issue number | 6 |
| Publication status | Published - 17.11.2022 |
| 43 |
Keywords
Pseudorandom generators
list recovery
local list decoding
pseudoentropy
quantified derandomization
ASJC Scopus subject areas
Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence
