<div dir="ltr"><div>Dear theorists,</div><div><br></div><div>I am writing to advertise a theory topics course that I'm teaching this quarter.<br><br></div><div><b>Title:</b> Derandomizing Space-Bounded Computation.</div><div><b>Meetings:</b> Tuesdays and Thursdays, 2:00pm - 3:20pm, JCL 011.</div><div><b>Course description:</b></div><div><b><br></b></div><div style="margin-left:40px">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.</div><div style="margin-left:40px"><br></div><div><b>Course webpage:</b> <a href="https://williamhoza.com/teaching/winter2025-derandomizing-space-bounded-computation/">https://williamhoza.com/teaching/winter2025-derandomizing-space-bounded-computation/</a></div><div><div><div><div><br clear="all"></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>Sincerely,<br></div><div>William Hoza</div></div></div></div></div></div></div></div>