BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1689
DTSTAMP:20260216T045736Z
SUMMARY:Proving "Undirected Connectivity in Logspace" in Logspace
DESCRIPTION:Speaker: Sasank Mouli (IIT Indore)\n\nAbstract: \nReingold (STO
 C '05) proved in his breakthrough result that the problem of Undirected Co
 nnectivity\, i.e. deciding whether nodes s and t are connected in a gi
 ven undirected graph G\, is in Logspace\, culminating incremental improve
 ments over a long series of works. In this talk\, we will discuss whether 
 Logspace can define and prove all the concepts involved in this result. Na
 mely\, is there a proof of "Undirected Connectivity in Logspace" in a syst
 em of Bounded Arithmetic that can only reason with concepts definable in L
 ogspace? We answer this question in the affirmative. To establish this res
 ult\, we use an alternative and arguably simpler proof of this result\, by
  Rozenman and Vadhan (APPROX-RANDOM '05). Additionally\, both proofs use e
 igenvalues and eigenvectors which are not known to be definable in Logspac
 e\, so we use the alternate and essentially equivalent concept of mixing r
 atios to formalize Rozenman and Vadhan's proof\, using results from Buss\,
  Kabanets\, Kolokolova\, Koucky (Ann. Pure and Applied Logic\, 2020) and M
 ihail (FOCS '89) to bridge the gap. The proof is then completed by applyin
 g fixes to other concepts outside of Logspace used in the proof such as sq
 uare roots and iterated matrix multiplication. Based on joint work with Sa
 m Buss\, Anant Dhayal\, Valentine Kabanets and Antonina Kolokolova. \nSho
 rt Bio: Sasank Mouli is an Assistant Professor at the Indian Institute of 
 Technology\, Indore. He received his PhD from the University of California
 \, San Diego and his Bachelors degree from the Indian Institute of Technol
 ogy\, Kanpur. His area of research is Proof Complexity. \n
URL:https://www.tcs.tifr.res.in/web/events/1689
DTSTART;TZID=Asia/Kolkata:20260220T160000
DTEND;TZID=Asia/Kolkata:20260220T170000
LOCATION:A-201 Seminar Room
END:VEVENT
END:VCALENDAR