The Lovasz Local Lemma and its Algorithmic Aspects

When: Monday, February 27, 2017
Where: PGH 232
Time: 11:00 AM

Speaker: Prof. Aravind Srinivasan, University of Maryland

Host: Dr. Gopal Pandurangan

The Lovasz Local Lemma is a simple and powerful probabilistic technique introduced by Erdos and Lovasz in 1975; the Lemma has emerged as a very useful addition to the algorithm designer's toolkit. Moser and Tardos have developed an elegant algorithmic version of the Lemma. I will survey some of the key ideas relating to the Lemma and Moser-Tardos, as well as connections to satisfiability, network routing, scheduling, and statistical physics. The talk will be self-contained and will not require any background on the Lovasz Local Lemma.

Bio:

Aravind Srinivasan is a Professor with the Department of Computer Science and the Institute for Advanced Computer Studies at the University of Maryland. He received his undergraduate degree from the Indian Institute of Technology, Madras, and his Ph.D. from Cornell University. He has also worked at Bell Labs. His research interests are in randomized algorithms, networking, social networks, combinatorial optimization, and computing in the service of society. He has published more than 110 papers in these areas, in journals including Nature, Journal of the ACM, IEEE/ACM Transactions on Networking, and the SIAM Journal on Computing. He is Editor-in-Chief of the ACM Transactions on Algorithms, Managing Editor for "Theory of Computing", and Associate Editor of "Networks".

Dr. Srinivasan is a Fellow of three professional societies: ACM, AAAS and IEEE. He received a Distinguished Alumnus Award from his alma mater IIT Madras. He also received the Distinguished Faculty Award from the Board of Visitors of the College of Computing, Mathematical, and Natural Sciences (University of Maryland) in 2016.