Sanjeev Arora

Sanjeev Arora is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C. Fitzmorris Professor of Computer Science at Princeton University, and his research interests include computational complexity theory, uses of randomness in computation, probabilistically checkable proofs, computing approximate solutions to NP-hard problems, geometric embeddings of metric spaces and machine learning.
His Ph.D. thesis on probabilistically checkable proofs received the ACM Doctoral Dissertation Award in 1995. He was awarded the Gödel Prize for his work on the PCP theorem in 2001 and again in 2010 for the discovery (concurrently with Joseph S. B. Mitchell) of a polynomial time approximation scheme for the euclidean travelling salesman problem. In 2008 he was inducted as a Fellow of the Association for Computing Machinery. In 2011 he was awarded the ACM Infosys Foundation Award, given to mid-career researchers in Computer Science. Arora has been awarded the Fulkerson Prize for 2012 for his work on improving the approximation ratio for graph separators and related problems (jointly with Satish Rao and Umesh Vazirani).
He is a coauthor (with Boaz Barak) of the book "Computational Complexity: A Modern Approach" and is a founder, and on the Executive Board, of Princeton's Center for Computational Intractability. (Source: Wikipedia)

Talk Title: 
Is Intractability a barrier for machine learning?
Talk Abstract: 

One of the frustrations of machine learning theory is that many of the underlying algorithmic problems are provably intractable (e.g., NP-hard or worse) or presumed to be intractable (e.g., the many open problems in Valiant's model). This talk will suggest that this seeming intractability may arise because many models used in machine learning are more general than they need to be. Careful reformulation as well as willingness to consider new models may allow progress. We will use examples from recent work: Nonnegative matrix factorization, Learning Topic Models, ICA with noise, etc.
(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant Sachdeva, as well as papers that are not mine)

Princeton University