Ketan Mulmuley
Encyclopedia
Ketan Mulmuley is a professor in the Department of Computer Science at the University of Chicago
, and a sometime visiting professor at IIT Bombay. He specializes in theoretical computer science
, especially computational complexity theory
, and in recent years has been working on "geometric complexity theory", an approach to the P versus NP problem through the techniques of algebraic geometry
, with Milind Sohoni of IIT Bombay . He is also known for his result with Umesh Vazirani
and Vijay Vazirani
that showed that "Matching is as easy as matrix inversion", in a paper that introduced the isolation lemma
.
He earned his PhD in computer science from Carnegie Mellon University
in 1985 under Dana Scott
, winning the 1986 ACM
Doctoral Dissertation Award for his thesis Full Abstraction and Semantic Equivalence. He also won a Miller fellowship at the University of California, Berkeley
for 1985–1987, and a Guggenheim Foundation Fellowship for the year 1999–2000.
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
, and a sometime visiting professor at IIT Bombay. He specializes in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, especially computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, and in recent years has been working on "geometric complexity theory", an approach to the P versus NP problem through the techniques of algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
, with Milind Sohoni of IIT Bombay . He is also known for his result with Umesh Vazirani
Umesh Vazirani
Umesh Virkumar Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
and Vijay Vazirani
Vijay Vazirani
Vijay Virkumar Vazirani is an Indian American Professor of Computer Science at Georgia Tech.He received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian...
that showed that "Matching is as easy as matrix inversion", in a paper that introduced the isolation lemma
Isolation lemma
The isolation lemma, also sometimes known as the isolating lemma, is a lemma in probability theory with several applications in computer science. It was introduced in a paper by Mulmuley, Vazirani and Vazirani, who used it to give a randomized parallel algorithm for the maximum matching...
.
He earned his PhD in computer science from Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
in 1985 under Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
, winning the 1986 ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Doctoral Dissertation Award for his thesis Full Abstraction and Semantic Equivalence. He also won a Miller fellowship at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
for 1985–1987, and a Guggenheim Foundation Fellowship for the year 1999–2000.