Computer Science Department Master Calendar

Back to Listing

William Hoza "Hitting Sets Give Two-Sided Derandomization of Small Space"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
In person 4403 Siebel Center for Computer Science or Online
Virtual
wifi event
Date
Nov 28, 2022   10:00 am  
Cost
William Hoza, UC Berkeley
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Phone
217-300-8564
Views
19
Originating Calendar
Computer Science Speakers Calendar

Join us in person 4403 Siebel Center for Computer Science or Online

Abstract: 

A "decision problem" is a problem where the answer is always "yes" or "no," e.g., the problem of determining whether a given number is prime. Suppose there's a randomized algorithm \(A\) that solves some decision problem with high probability using a small amount of memory. Does that automatically mean there's a deterministic algorithm that solves the same problem using a similar amount of memory? In other words, is it always possible to "derandomize" any low-memory decision algorithm? Computer scientists think so, but we're not sure how to prove it.

If \(A\) has the special feature that it never gives false positives, derandomization is potentially easier. Some of the most promising approaches treat \(A\) as a "black box," meaning that the deterministic algorithm would just simulate \(A\) in a few carefully crafted scenarios and then figure out the correct answer based on what \(A\) outputs in those scenarios. In this paper, we prove that if it is possible to derandomize all low-memory decision algorithms that never give false positives in a black-box manner, then it is possible to derandomize all low-memory decision algorithms, whether they give false positives or not.

Joint work with Kuan Cheng. CCC 2020. https://theoryofcomputing.org/articles/v018a021/.

 

link for robots only