Derandomizing Space-Bounded Computation (Part 2) @SimonsInstitute
Derandomizing Space-Bounded Computation (Part 2)  @SimonsInstitute
Uploaded September 2026 | Updated November 2026, 1 day ago
William Hoza (University of Chicago)
https://simons.berkeley.edu/talks/william-hoza-university-chicago-2026-09-02
Joint Boot Camp: Spectral Theory Beyond Graphs + Pseudorandomness and High-Dimensional Expansion

We present an introduction to the "L vs. BPL" problem, which asks whether randomness is ever necessary for space-efficient computation. We highlight four approaches to the problem: the "INW approach," the "Nisan approach," the "iterated restrictions approach," and the "inverse Laplacian approach."
Derandomizing Space-Bounded Computation (Part 2)Resonances on geometrically finite graphs and buildingsInference-Time Algorithms: A Theoretical Lens on Tractability and Error PropagationAligning Evaluation Incentives to Reduce HallucinationATHENA: Steering Generative Models toward Better Visual ReasoningReliable Language GenerationStrong Convergence (Part I)Expanding GroupsLinear hashing and friendsMy Favorite Expanders | Richard M. Karp Distinguished LectureMatching Correlated Random Geometric GraphsFault-Tolerant Quantum Computation with Adversarial Errors
Simons Institute for the Theory of Computing |

Derandomizing Space-Bounded Computation (Part 2)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER