COCOON 2016, Aug. 2-4, 2016, Ho Chi Minh City, Vietnam
The 22nd International Computing and Combinatorics Conference


Aravind Srinivasan: Algorithmic aspects of the Lovasz Local Lemma

Department of Computer Science,
University of Maryland at College Park,
College Park, MD 20742, USA

HTML5 Icon

Aravind Srinivasan is a Professor with the Department of Computer Science and the Institute for Advanced Computer Studies at the University of Maryland, College Park. He received his undergraduate degree from the Indian Institute of Technology, Madras, and his Ph.D. from Cornell University, both in Computer Science. He was a postdoctoral researcher at the Institute for Advanced Study in Princeton and at DIMACS. He has also worked in industrial research, at Bell Labs. Aravind Srinivasan's research interests are in randomized algorithms, networking, social networks, and combinatorial optimization, as well as in the growing confluence of algorithms, networks, and randomness, in fields including the social Web, machine learning, public health, biology, and energy. He has published more than 100 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, Associate Editor of Networks, and has served on the program committees of various conferences.

His papers have been (co-)recipients of the Best Paper/Best Student Paper Awards at various conferences in areas including algorithms, networking, and social 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. Aravind Srinivasan serves as Vice Chair of the IEEE Technical Committee on the Mathematical Foundations of Computing.

Abstract: The Lovasz Local Lemma (LLL) is a powerful probabilistic tool in computer science and in combinatorics. Starting with the breakthrough of Moser and Tardos in 2009, there has been much progress in our understanding of the algorithmic aspects of the LLL. I will survey some of this work; prior knowledge of the LLL will not be necessary.

Van Vu: Dictionary Learning with few samples via matrix concentration

Percey F. Smith Professor of Mathematics
Mathematics Dept.
Yale University
New Haven, CT 06520, USA

HTML5 Icon

Van Vu obtained his PhD in Mathematics in 1998 at Yale under the direction of Laszlo Lovasz. He worked at the IAS (Princeton), Microsoft Research, UC San Diego and Rutgers Univ. before moving to Yale in 2011, where he holds the Percy Smith chair in mathematics. Vu's research interest includes combinatorics, probability, number theory and computer science. He was awarded the Polya prize in 2008 for his works on concentration of measure and the Fulkerson prize in 2012 for his works on random graphs. Dr Vu is a Sloan fellows and a fellows of the AMS. In 2007, he was the director of the Arithmetic Combinatorics program at the Institute for Advance Studies (Princeton). He was an invited speaker at the International Congress of Mathematicians (ICM) in 2014 and a Medallion speaker at the 8th World Congress in Statistics and Probability (2012).

Abstract: Let A be an n by n matrix, X be an n by p matrix and Y=AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spielman, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large compared to n. Their method works for p at least quadratic in n, and they conjectured that a linear dependence suffices (up to a logarithmic correction). In this talk, we discuss our recent solution of this conjecture. A key ingredient is a new random matrix concentration result, the proof of which is of independent interest, as it shows a simple way to modify the regular epsilon-net argument and avoid the standard union bound. Joint work with K. Luh (Yale).