Theory Seminar - Ted Pyne

— 2:00pm

Location:
In Person - Gates Hillman 7101

Speaker:
TED PYNE , Ph.D. StudentElectrical Engineering and Computer Science DepartmentMassachusetts Institute of Technology
https://sites.google.com/view/tedpyne/

When Connectivity is Hard, Random Walks are Easy (with Nondeterminism)

Two well-studied problems on graphs 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 (STOC 2025). 

For More Information:
korinna@cmu.edu

Add event to Google
Add event to iCal