Derandomizing Space-Bounded Computation (Part 1) @SimonsInstitute
Derandomizing Space-Bounded Computation (Part 1)  @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-01
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 1)Probability, Information, and DiscrepancyCondensers/extractors for block sources surveyStrongly explicit sorting on HDXsQuantifying Reliability in AI: Hallucinations and UncertaintySpectral approximation of directed graphs and moreHigh-Accuracy Sampling for Diffusion Models and Log-Concave DistributionsExplicit free expandersScore-Based Generative Modeling without Diffusion: Langevin MCMC All the WayThe Computer in the Sky | Theoretically SpeakingHitting-set generators for low-degree F2-polynomials with almost optimal densityHow Haar Is It to Look Random?
Simons Institute for the Theory of Computing |

Derandomizing Space-Bounded Computation (Part 1)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER