BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1706
DTSTAMP:20260504T054522Z
SUMMARY:Markov Chains with Rewinding
DESCRIPTION:Speaker: Madhu Sudan (Harvard University)\n\nAbstract: \nThe ta
 sk of trying to identify the (most likely) Markov Chain that generates a s
 equence is a classical problem in probabilistic inference. In this talk we
  introduce a twist to this classical problem motivated by the tasking of l
 earning/understanding the power of randomized algorithms. In our mode\, wh
 ich we call Markov Chains with Rewinding\, the learner either gets to ask 
 the chain to continue from its current state and produce the next signal\,
  or gets to rewind the chain to a previous time and then proceed from ther
 e. This increases the information one can learn about the underlying chain
 \; and techniques to bound the amount of information learned turn out to b
 e a powerful tool in the analysis of sublinear time algorithms (notably in
  the works of Behnezhad\, Roghani and Rubinstein\, STOC 2023\, FOCS 2023\,
  and STOC 2024). While this model arose implicitly in these previous works
 \, in this work we study this systematically for the first time and develo
 p rewinding strategies that are competitive with the best possible ones in
  terms of the number of signals needed to identify the chain. Along the wa
 y we identify an important subclass of rewinding strategies\, namely non-a
 daptive ones\, and show their power.In the talk I will introduce the model
 \, explain how special cases (involving a constant number of states) play 
 a role in many previous lower bounds\, before turning to our general analy
 ses.Based on this joint work with Amir Azarmehr\, Soheil Behnezhad\, Alma
  Ghafari (all at Northeastern U.)\nShort Bio: Madhu Sudan is Gordon McKay 
 Professor at Harvard's John A. Paulson School of Engineering and Applied S
 ciences. He got his B.Tech. from IIT Delhi and Ph.D. from UC Berkeley and 
  previously held positions at IBM Research\, MIT\, and Microsoft Research
 . His research focuses on the mathematical foundations of communication an
 d computation in general\, and in particular on questions about probabilis
 tically checkable proofs\, list decoding of error correcting codes\, prope
 rty testing\, sublinear time algorithms and communication in the presence 
 of uncertainty. \n
URL:https://www.tcs.tifr.res.in/web/events/1706
DTSTART;TZID=Asia/Kolkata:20260519T160000
DTEND;TZID=Asia/Kolkata:20260519T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR