Microsoft Researcher to Receive ACM SIGACT Knuth Prize

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

 

Lance Fortnow							Virginia Gold
ACM SIGACT Chair							ACM
847-579-9310							212-626-0505
[email protected]							[email protected]

 

 Printable PDF

 

NEW YORK, April 26, 2011 – The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)  will present its 2011 Knuth Prize to Ravi Kannan of Microsoft Research Labs India for developing influential algorithmic techniques aimed at solving long-standing computational problems.  Kannan’s contributions address the challenges of computation with massive data that characterize today’s information-driven environment.  His foundational work spans many areas of theoretical computer science including lattices and their applications, geometric algorithms, machine learning, and computational linear algebra. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the "father" of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC), held as part of the Federated Computing Research Conference (FCRC), June 7, 2011, in San Jose, CA. Kannan will give the Knuth Prize Lecture to an FCRC plenary audience. 

Much of Kannan’s work has focused on efficient algorithms for mathematical and geometric problems in computer science.  One of his research papers, published in 1990, has been called by some one of the most remarkable algorithmic achievements ever. It addresses the issue of easy formulas for volumes of simple three-dimensional objects like spheres and cubes. The paper, A random polynomial-time algorithm for approximating the volume of convex bodies, written with Martin Dyer of the University of Leeds and Alan Frieze of Carnegie Mellon University, shows how to efficiently produce estimates of the volumes of arbitrary high-dimensional convex sets.  The method they developed uses random walks to do geometric sampling, a technique now central to the theory of algorithms. The winner of the Fulkerson Prize in Discrete Mathematics in 1991, this paper also introduced the notion of geometric isoperimetry, a measure of an area marked by boundaries, to theoretical computer science.  

In his breakthrough 1991 paper, Kannan tackled the Frobenius problem, which seeks to find the largest number that cannot arise from a combination of certain denominations.  For example, it is not possible to make seven dollars from a combination of three and five dollar bills, but every amount eight and higher is possible. Kannan’s paper gave the first efficient algorithm for finding this Frobenius number. This algorithm also led to important developments in integer programming and quantifier elimination.           

Kannan was also cited for his research on algorithms for finding low-rank approximations to matrices, applicable to principal component analysis, which was conducted with Frieze and Santosh Vempala, then of Carnegie Mellon University.  In a 1999 paper with Frieze, Kannan introduced the Weak Regularity Lemma, which has become an important new combinatorial tool in areas including sublinear algorithms, streaming algorithms, and graph limits. 

A principal Researcher at Microsoft Research India, Kannan leads the algorithms research group.  He is the also the first adjunct faculty of Computer Science and Automation at the Indian Institute of Science.  Before joining Microsoft, he was a professor of computer science and of applied mathematics at Yale University.  He previously taught at Carnegie Mellon University and the Massachusetts Institute of Technology. 

A graduate with a B. Tech from the Indian Institute of Technology in Bombay, Kannan earned a Ph.D. at Cornell University.  

The Knuth Prize is given every 18 months by ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computer Science and includes a $5,000 award. 

 

About ACM

ACM, the Association for Computing Machinery www.acm.org is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.  

 

About SIGACT

The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science.  The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.