[Theory] UC Theory Seminar: a reminder

[Alexander Razborov via Theory]

Ted Pyne
Massachusetts Institute of Technology
 
 
  
Tuesday, May 20, 2025, at 3:30pm
Kent Chemical Laboratory, Room 102
 
 
 
Title: When Connectivity is Hard, Random Walks are Easy (with Nondeterminism)
 
 
Abstract: Two well-studied graph problems are to 1: determine s->t connectivity, and 2: estimate the behavior of random walks. Currently, there is no algorithm for (1) that runs in polynomial time and strongly sublinear space, and no algorithm for (2) that runs in nondeterministic logspace. We show that for every graph, at least one of these problems is solvable more efficiently than the state of the art. Our results build on recent work on distinguish-to-predict transformations (Li, Pyne, Tell) and bootstrapping systems (Chen, Tell). As a consequence, either randomized linear space can be derandomized, or a time- and space-efficient simulation of nondeterministic linear space holds. Joint work with Dean Doron, Roei Tell, and Ryan Williams (to appear in STOC 2025).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250519/f9dbbc4c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 544066 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250519/f9dbbc4c/attachment-0001.png>