Date & Time:
April 4, 2023 2:00 pm – 3:00 pm
Crerar 298, 5730 S. Ellis Ave., Chicago, IL,
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.


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.


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

Michael Franklin
UChicago CS News

Mike Franklin, Dan Nicolae Receive 2023 Arthur L. Kelly Faculty Prize

Jun 02, 2023
UChicago CS News

Computer Science Class Shows Students How To Successfully Create Circuit Boards Without Engineering Experience

May 17, 2023
UChicago CS News

Chicago Public Schools Student Chris Deng Pursues Internet Equity with University of Chicago Faculty

May 16, 2023
UChicago CS News

CS Chair Michael Franklin Elected to the American Academy of Arts & Sciences

Apr 28, 2023
UChicago CS News

UChicago CS Researchers Shine at CHI 2023 with 12 Papers and Multiple Awards

Apr 19, 2023
UChicago CS News

New Prototypes AeroRigUI and ThrowIO Take Spatial Interaction to New Heights – Literally

Apr 18, 2023
UChicago CS News

PhD Student Kevin Bryson Receives NSF Graduate Research Fellowship to Create Equitable Algorithmic Data Tools

Apr 14, 2023
UChicago CS News

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023
UChicago CS News

UChicago / School of the Art Institute Class Uses Art to Highlight Data Privacy Dangers

Apr 03, 2023
UChicago CS News

UChicago, Stanford Researchers Explore How Robots and Computers Can Help Strangers Have Meaningful In-Person Conversations

Mar 29, 2023
UChicago CS News

Virtual Bakery Game Serves Up Both Cupcakes and Quantum Concepts For K-12 Students

Mar 27, 2023
Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
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