<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">Ted Pyne</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">Massachusetts Institute of Technology</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> <img width="283" height="352" id="Picture_x0020_1" src="cid:7DC18981-EBC2-424D-ABF2-55C4402F4D9A" alt="image001.png" style="width: 2.9479in; height: 3.6666in;"></span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr">May 20</span><span dir="ltr">, 202</span><span dir="ltr">5,</span><span dir="ltr"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background: yellow;">Kent Chemical Laboratory, Room 102</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Title:</span></i></b><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><span style="font-size: 11pt; color: rgb(33, 33, 33);">When Connectivity is Hard, Random Walks are Easy (with Nondeterminism)</span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Abstract:</span></i></b><span style="color: rgb(33, 33, 33);"> </span><span style="font-size: 11pt; color: rgb(33, 33, 33);">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,<span class="apple-converted-space"> </span><span class="outlook-search-highlight">Pyne</span>, 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).</span></p><div dir="ltr"></div></body></html>