The task of trying to identify the (most likely) Markov Chain that generates a sequence is a classical problem in probabilistic inference. In this talk we introduce a twist to this classical problem motivated by the tasking of learning/understanding the power of randomized algorithms. In our mode, which 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 there. This increases the information one can learn about the underlying chain; and techniques to bound the amount of information learned turn out to be 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 develop rewinding strategies that are competitive with the best possible ones in terms of the number of signals needed to identify the chain. Along the way we identify an important subclass of rewinding strategies, namely non-adaptive 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 analyses.Based on this joint work with Amir Azarmehr, Soheil Behnezhad, Alma Ghafari (all at Northeastern U.)
Short Bio: Madhu Sudan is Gordon McKay Professor at Harvard's John A. Paulson School of Engineering and Applied Sciences. 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 and computation in general, and in particular on questions about probabilistically checkable proofs, list decoding of error correcting codes, property testing, sublinear time algorithms and communication in the presence of uncertainty.
