- Ravi Kannan
(Microsoft Research)
Randomized Algorithms in Linear Algebra
Linear Algebra computations on large matrices are expensive. Computing instead with a random sub-matrix is a natural idea. Theorems from the 90’s bounded the error in this provided sampling probabilities are proportional to squared length. There has been a substantial body of work sinceon different sampling schemes which achieve much better bounds. Random Projections, Probabilities based on Leverage Scores, Subspace Embeddings are some examples. Recent work also extends the algorithms to Streaming and Distributed Data models which are appropriate for massive modern matrices. The talk will describe theorems, applications and challenges in the area.
Before joining Microsoft, Kannan was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University. He has also taught at CMU and MIT. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) presented its 2011 Knuth Prize to Ravi Kannan for “developing influential algorithmic techniques aimed at solving long-standing computational problems.” He is the recipient of the 1992 Fulkerson Prize in Discrete Mathematics. His research interests include Algorithms, Theoretical Computer Science and Discrete Mathematics as well as Optimization. His work has mainly focused on efficient algorithms for problems of a mathematical (often geometric) flavor that arise in Computer Science. He has worked on algorithms for integer programming and the geometry of numbers, random walks in n-space, randomized algorithms for linear algebra and learning algorithms for convex sets.
- Ronitt Rubinfeld
(MIT and Tel Aviv University)
Testing properties of distributions over big domains
We describe an emerging research direction regarding the complexity of testing global properties of discrete distributions, when given access to only a few samples from the distribution. Such properties might include testing if two distributions have small statistical distance, testing various independence properties, testing whether a distribution has a specific shape (such as monotone decreasing, k-modal, k-histogram, monotone hazard rate,…), and approximating the entropy. We describe bounds for such testing problems whose sample complexities are sublinear in the size of the support.
Ronitt received her Bachelors degree at the University of Michigan and her Ph.D. from U.C. Berkeley in 1990. Ronitt held postdoctoral researcher positions at Princeton University and Hebrew University. In 1992, she joined the faculty of the Computer Science Department at Cornell University, where she was an ONR Young Investigator, a Sloan Research Fellow, the 1995 Cornell Association for Computer Science Undergraduates Faculty of the Year, and a recipient of the Cornell College of Engineering Teaching Award. From 1999 to 2003, Ronitt was at NEC Research Laboratories. Ronitt has been at MIT since 2004 and at Tel Aviv University since 2008.
Ronitt’s research interests revolve around sublinear time algorithms. Her work focuses on the question of what can be understood about data by looking at only a very small portion of it. Much of her current work also concentrates on testing properties and estimating parameters of distributions over very large domains. Ronitt was a Radcliffe Fellow in 2004, and is a fellow of the ACM.