[Colloquium] TODAY William Hoza (Berkeley) Pseudorandomness and Space Complexity: New Methods, New Insights, and New Milestones

[Holly Santos]

Department of Computer Science Seminar

William Hoza
Postdoctoral Fellow
University of California, Berkeley

Tuesday April 4th
2:00pm - 3:00pm
In Person: John Crerar Library 298

Zoom:
https://uchicagogroup.zoom.us/j/96948783920?pwd=VWVkZ0ZFd1o5OTJkd2dKN3dpWXhlQT09

Meeting ID: 969 4878 3920
Passcode: 161298

Title: Pseudorandomness and Space Complexity: New Methods, New Insights, and New Milestones

Abstract:
Algorithm designers often introduce random choices into their algorithms in an effort to improve efficiency. However, random bits cannot necessarily be produced for free, so deterministic algorithms are preferable to randomized algorithms, all else being equal. Is randomness ever truly necessary for efficient computation? What, ultimately, is the role of randomness in computing?

In this talk, I will discuss the "L = BPL" conjecture, which says that for every clever randomized algorithm, there is an even cleverer deterministic algorithm that does the same job with roughly the same space complexity. The most traditional approach for trying to prove this conjecture is based on pseudorandom generators (PRGs), which have additional applications beyond derandomizing algorithms. There are also other approaches based on variants of the PRG concept, most notably "weighted PRGs" and "hitting set generators." I will give an overview of my contributions in this area (with collaborators), consisting of new constructions and applications of these three types of generators.

Bio:
William Hoza is a postdoctoral fellow at the University of California, Berkeley through the Simons Institute for the Theory of Computing. His PhD is from the University of Texas at Austin, where he was advised by David Zuckerman. He studies topics in computational complexity theory, especially pseudorandomness and derandomization.

[9897C5C6-41A3-4DEC-82CE-0B0926E4AE96.jpeg]

----
Holly Santos
Executive Assistant to Michael J. Franklin, Chairman
Department of Computer Science
The University of Chicago
5730 S Ellis Ave-217   Chicago, IL 60637
P: 773-834-8977
hsantos at uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230404/4ac0cb47/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 9897C5C6-41A3-4DEC-82CE-0B0926E4AE96.jpeg
Type: image/jpeg
Size: 26285 bytes
Desc: 9897C5C6-41A3-4DEC-82CE-0B0926E4AE96.jpeg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230404/4ac0cb47/attachment-0001.jpeg>