Date & Time:
April 4, 2023 2:00 pm – 3:00 pm
Location:
Crerar 298, 5730 S. Ellis Ave., Chicago, IL,
Register
04/04/2023 02:00 PM 04/04/2023 03:00 PM America/Chicago William Hoza (Berkeley)-Pseudorandomness and Space Complexity: New Methods, New Insights, and New Milestones Crerar 298, 5730 S. Ellis Ave., Chicago, IL,

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.

Speakers

William Hoza

Postdoctoral Fellow, University of California, Berkeley

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.

Registration

Register
04/04/2023 02:00 PM 04/04/2023 03:00 PM America/Chicago William Hoza (Berkeley)-Pseudorandomness and Space Complexity: New Methods, New Insights, and New Milestones Crerar 298, 5730 S. Ellis Ave., Chicago, IL,

Related News & Events

simulated Roblox chat
UChicago CS News

Helping Elementary School Children Learn About Digital Privacy and Security With Micro-Lessons

Mar 25, 2025
grant ho writing on white board
UChicago CS News

New Study Reveals Gaps in Common Types of Cybersecurity Training

Mar 24, 2025
headshot
UChicago CS News

Jasmine Lu on Sustainable Computing: Rethinking E-Waste and Innovation

Mar 18, 2025
Pedro giving speech
UChicago CS News

Pedro Lopes Honored with 2025 IEEE VGTC Virtual Reality Significant New Researcher Award

Mar 13, 2025
ai generated network traffic
UChicago CS News

University of Chicago Researchers Revolutionize Network Traffic Generation with AI Breakthrough

Mar 12, 2025
UChicago CS News

Federal budget cuts threaten to decimate America’s AI superiority—and other countries are watching

Feb 25, 2025
Netflix logo on phone screen
UChicago CS News

The Hidden Cost of Netflix’s Autoplay: A Study on Viewing Patterns and User Control

Feb 25, 2025
Raul Castro Fernandez
UChicago CS News

Raul Castro Fernandez among six UChicago scientists awarded prestigious Sloan Fellowships in 2025

Feb 18, 2025
UChicago CS News

Quantum Leap: New Research Reveals Secrets of Random Quantum Circuits

Feb 04, 2025
UChicago CS News

Fred Chong from the Department of Computer Science Named ACM Fellow for Contributions to Quantum Computing

Jan 22, 2025
UChicago CS News

Rethinking AI as a Thought Partner: Perspectives on Writing, Programming, and More

Jan 16, 2025
UChicago CS News

UChicago Partners On New National Science Foundation Large-Scale Research Infrastructure For Education

Dec 10, 2024
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube