[Theory] Theory topics course: "Derandomizing Space-Bounded Computation"

[William Hoza via Theory]

Dear theorists,

I am writing to advertise a theory topics course that I'm teaching this
quarter.

*Title:* Derandomizing Space-Bounded Computation.
*Meetings:* Tuesdays and Thursdays, 2:00pm - 3:20pm, JCL 011.
*Course description:*

What is the relationship between space complexity and randomness? Both
space and random bits can be considered "expensive" computational
resources, so it is desirable to use as little of each as possible. One of
the major goals of computational complexity theory is to prove that every
randomized decision algorithm can be "derandomized" (i.e., converted into a
deterministic algorithm) without increasing its space complexity by more
than a constant factor. Complexity theorists have made a great deal of
progress toward proving this conjecture over the past several decades, and
it is an active and exciting area of research today. In this seminar
course, we will study both classic and cutting-edge work on this problem
and closely related problems. This will involve topics such as pseudorandom
generators, expander graphs, Laplacian solvers, and the Fourier analysis of
Boolean functions.

*Course webpage:*
https://williamhoza.com/teaching/winter2025-derandomizing-space-bounded-computation/

Sincerely,
William Hoza
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250107/ea2b7b2d/attachment.html>