Principal Researcher, Microsoft Research, India; Adjunct Professor of Computer Science, Carnegie Mellon University
Distinguished Lecture Series
Vectors, Sampling and Massive Data
Modeling data as high-dimensional (feature) vectors is a staple in Computer Science, its use in ranking web pages reminding us again of its effectiveness. Algorithms from Linear Algebra (LA) provide a crucial toolkit. But, for modern problems with massive data, these algorithms may take too long. Random sampling to reduce the size suggests itself. I will give a from-first-principles description of the LA connection, then discuss sampling techniques developed over the last decade for vectors, matrices and graphs. Besides algorithmic efficiency, sampling leads to sparsification and compression of data.
Ravi Kannan's research areas include Algorithms, Optimization and Probability. He has been on the faculty at CMU, MIT, and was the William Lanman Professor of Computer Science at Yale University before moving to Microsoft Research, India, where he is presently. Among his honors are the 2011 ACM-SIGACT Knuth Prize and the Fulkerson Prize in 1992.