Seminars

View all Seminars  |  Download ICal for this event

Noise Thresholds for Nearest Neighbor Search (NNS) in high dimensions.

Series: Department Seminar

Speaker: Prof. Ravindran Kannan. Theoretical Computer Scientist

Date/Time: Feb 06 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
We solve the NNS problem in the well-studied semi-random model. The
twist is that we are given only noisy data. The noise amplitude is high and the
NN in the noisy data is different from NN in the noise-free data. Our algorithm
is natural and finds the NN in the noise-free data provided the noise is upper
bounded. We prove that the bound is tight. The proofs use known results on
perturbation of singular spaces of a matrix as well as bounds on spectral norms
of random matrices.

Speaker Bio:
Ravindran (Ravi) Kannan (Tamil: ரவீந்திரன் கண்ணன்); born 12 March 1953, is a theoretical computer scientist. His work has mainly focused on efficient algorithms for problems of a mathematical (often geometric) flavor that arise in Computer Science, Machine Learning and Optimization. Ravi was a Principal Researcher at Microsoft Research Lab, India. Before joining Microsoft, he was William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University. Prior to that he has been on the faculty of 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.[1] Ravi Kannan did his B.Tech at IIT, Bombay. He received his PhD in 1980 at Cornell University under Leslie Earl Trotter, Jr.[2] Awards and honors: Joint Winner of the 1991 Fulkerson Prize in Discrete Mathematics for his work on the volumes of convex bodies.[3] Knuth Prize 2011 for developing influential algorithmic techniques aimed at solving long-standing computational problems.[1] In 2017 he became a Fellow of the Association for Computing Machinery.[4] Member, American Academy of Arts and Sciences Member, National Academy of Sciences https://en.wikipedia.org/wiki/Ravindran_Kannan

Host Faculty: Prof. Chiranjib Bhattacharyya