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

Card Image 22624dd

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

Card Image 87c2d61
Card Image
UChicago CS News

Alumni Spotlight: Get To Know Emily Wenger, a 2023 CS Graduate Who Was Just Named To The Forbes 30 Under 30 List

Card Image c093dd5
Card Image
UChicago CS News

Three UChicago PhD Students From The Department of Computer Science Named To Forbes 30 Under 30 List

Card Image 290684b
Card Image
UChicago CS News

High School Students In The Collegiate Scholars Program Get To Know Robots

Card Image f088c40
Card Image
UChicago CS News

AxLab Features Multidisciplinary Works at World’s Largest Art and Technology Festival

Card Image 4a51351
Card Image
UChicago CS News

UChicago Undergrad Analyzes Machine Learning Models Used By CPD, Uncovers Lack of Transparency About Data Usage

Card Image 6c45e07
Card Image
UChicago CS News

CS Alumni Spotlight: Former Student Andrew McNutt Talks Visualization Career, Lessons From UChicago, And The Road From PhD to Tenure Track at University of Utah

Card Image 9b1a6ed
Card Image
UChicago CS News

UChicago CS Chair, Faculty, and Students Inducted Into Samsung Hall Of Fame For Identifying Vulnerability In SmartTVs

Card Image a88e05c
Card Image
UChicago CS News

CS PhD Student J. Gregory Pauloski Named Recipient of 2023 ACM-IEEE CS George Michael Memorial HPC Fellowship

UChicago CS News

Research Suggests That Privacy and Security Protection Fell To The Wayside During Remote Learning

A qualitative research study conducted by faculty and students at the University of Chicago and University of Maryland revealed key...
Card Image c3138cb
Card Image
UChicago CS News

Five UChicago CS students named to Siebel Scholars Class of 2024

Card Image bb11752
Card Image
UChicago CS News

UChicago Computer Scientists Design Small Backpack That Mimics Big Sensations

Card Image c0f159d
Card Image
UChicago CS News

UChicago Researchers Win Internet Defense Prize and Distinguished Paper Awards at USENIX Security

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