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

Four Students Receive Honorable Mention in CRA Undergraduate Research Awards

Mar 25, 2024

Navigating the Intersection of Technology and Public Policy: The Journey of Ranya Sharma at UChicago

Mar 21, 2024

Assistant Professor Aloni Cohen Receives Prestigious Award for Groundbreaking Research in Machine Learning Complexity

Mar 20, 2024

Haifeng Xu named a AI2050 Early Career Fellow

Mar 11, 2024

FabRobotics: The Fusion of 3D Printing and Mobile Robots

Feb 27, 2024

Professor Andrew A. Chien on the Environmental Impacts of Technology

Feb 26, 2024

Assistant Professor Yanjing Li Awarded NSF CAREER Grant for Innovative Computer Architecture and Deep Learning Research

Feb 26, 2024

Prof. Rebecca Willett awarded the SIAG DATA Career prize

Feb 21, 2024

Argonne scientists use AI to identify new materials for carbon capture

Feb 19, 2024

Alumni Spotlight: Dixin Tang, Assistant Professor of Computer Science at UT Austin

Feb 05, 2024

NetMicroscope Uses AI to Improve Network Monitoring for a Better Internet Experience

Feb 01, 2024

NeurIPS 2023 Award-winning paper by DSI Faculty Bo Li, DecodingTrust, provides a comprehensive framework for assessing trustworthiness of GPT models

Feb 01, 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