Speakers

The Symposium will feature lectures from three prominent researchers in the field of theoretical computer science.

• Ronitt Rubinfeld, Massachusetts Institute of Technology and Tel Aviv University
• Russell Impagliazzo, University of California, San Diego
• Sanjeev Arora, Princeton University
  
  

Ronitt Rubinfeld Professor, Electrical Engineering and Computer Science Massachusetts Institute of Technology and Tel Aviv University "Something for Almost Nothing: Recent Advances in Sublinear Time Algorithms"

Abstract:
We have long considered showing the existence of a linear time algorithm for a problem to be the gold standard of achievement.  Indeed, at first thought, it is hard to imagine doing better than that, since for a nontrivial problem, any algorithm must consider all of the input in order to make a decision.  However, as extremely large data sets are pervasive, it is natural to wonder what one can do in *sublinear* time. Over the past decade, several surprising advances have been made on designing such algorithms. This talk will contain a nonexhaustive survey of this emerging area, highlighting recent progress and directions for further research.

Bio:
Ronitt Rubinfeld grew up in Ann Arbor,  receiving her undergraduate degree at the University of Michigan and her  PhD at the University of California, Berkeley. She held postdoctoral positions at DIMACS and the Hebrew University at Jerusalem. After several years as a faculty member at Cornell University and a senior research scientist at NEC Research Institute, she is currently on the faculties of MIT and Tel Aviv University. She has been a recipient of the ONR Young Investigator award, NSF CAREER Award, Sloan Fellowship, Cornell Association for Computer Science Undergraduates Faculty of the Year award and a Cornell College of Engineering Teaching award. She was an invited speaker at the International Congress of Mathematicians in 2006. Her research focuses on sub-linear time algorithms for big datasets. 

 

Russell Impagliazzo Professor, Computer Science and Engineering University of California, San Diego "Meta-Algorithms: Links between Algorithm Design and Lower Bounds"

Abstract:
Meta-algorithms are computational problems whose inputs are computational devices. Important examples are Circuit Satisfiability, generic derandomization, polynomial identity testing, and learning. There is an intuitive connection between finding meta-algorithms and proving circuit lower bounds, because both require an understanding of circuits. Work in complexity theory has proved formal versions of this connection, showing that in some circumstances, lower bounds imply efficient meta-algorithms and vice versa.

We will survey some of this work, and the tools used to prove such connections. Hardness vs. randomenss (Yao, AjtaiWigderson, NisanWigderson, BabaiFortnowNisanWigderson, ImpagliazzoWigderson, etc.), shows how to convert hard functions into pseudo-random generators and hence solve generic derandomization problems. The easy witness method of Kabanets and Impagliazzo, Kabanets and Wigderson can be used to prove a partial converse, converting any algorithm for generic derandomization into a circuit lower bound. Kabanets and Impagliazzo extended this connection to algebraic circuits, showing that any deterministic polynomial time algorithm for polynomial identity testing yields either a Boolean or algebraic circuit lower bound. Finally, Williams extended this to Satisfiability, showing that any non-trivial improvement over exhaustive search for Satisfiability yields a circuit lower bound. He used this to actually prove a circuit lower bound for ACC by giving an improved Satisfiability algorithm for ACC circuits.

We will sketch the above results, and show how each built on the others. In particular, we will look at the various "flips," techniques that start with an upper bound assumption and obtain a lower bound conclusion, and vice versa.

Bio:
Russell Impagliazzo joined the UCSD in faculty in 1989 after receiving his Ph.D. in mathematics from UC Berkeley. His main research interests are randomized algorithms, pseudo-random gen-
erators, the theory of cryptography, lower bounds, and proof complexity. He has been an NSF Young Investigator, a Sloan Fellow, a Fulbright Scholar, a Guggenheim Fellow, and he is currently a Simons Fellow. He is a frequent member of program committees for conferences on the theory of computing, including FOCS, STOC, Computational Complexity, and Crypto. His joint work with Kabanets and Wigderson won a Best Paper Award from the Computational Complexity Conference, and joint work with Kabanets won a Best Paper Award at STOC. His work with Hastad, Levin and Luby won an award for an Outstanding Paper from SIAM.

 

Sanjeev Arora Charles C. Fitzmorris Professor of Computer Science Princeton University "Is Machine Learning Easy?"

Abstract:
Machine learning is a flourishing field with a plethora of algorithmic techniques. In many cases, we have no provable guarantees on the performance of these algorithms/heuristics – neither on their running time, nor on the quality of solutions they return. In fact in many settings, the underlying algorithmic problems are provably intractable (e.g., NP-hard or worse)! 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. We will use examples from our 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.)

Bio:
Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area spans several areas of theoretical Computer Science. He has received the ACM-EATCS Gödel Prize (in 2001 and 2010), the ACM Infosys Prize for mid career scientists (in 2012), the Fulkerson Prize (2012), and fellowships form the Simons and Packard Foundations.