Narendra Karmarkar


Narendra Krishna Karmarkar is an Indian mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.
He invented one of the first provably polynomial time algorithms for linear programming, which is generally referred to as an interior point method. The algorithm is a cornerstone in the field of Linear Programming. He published his famous result in 1984 while he was working for Bell Laboratories in New Jersey.

Biography

Karmarkar received his B.Tech in Electrical Engineering from IIT Bombay in 1978, M.S. from the California Institute of Technology in 1979, and Ph.D. in Computer Science from the University of California, Berkeley in 1983 under the supervision of Richard M. Karp.
Karmarkar was a post-doctoral research fellow at IBM research, Member of Technical Staff and fellow at Mathematical Sciences Research Center, AT&T Bell Laboratories, professor of mathematics at M.I.T., at Institute for Advanced study, Princeton, and Homi Bhabha Chair Professor at the Tata Institute of Fundamental Research in Mumbai from 1998 to 2005. Karmarkar was funded by Ratan Tata to create Computational Research labs in Pune. He created a team of 50 plus Phd researchers for this team. He was the scientific advisor to the chairman of the TATA group. He is currently working on a new architecture for supercomputing.

Work

Karmarkar's algorithm

Karmarkar's algorithm solves linear programming problems in polynomial time. These problems are represented by a number of linear constraints involving a number of variables. The previous method of solving these problems consisted of considering the problem as a high dimensional solid with vertices, where the solution was approached by traversing from vertex to vertex. Karmarkar's novel method approaches the solution by cutting through the above solid in its traversal. Consequently, complex optimization problems are solved much faster using the Karmarkar algorithm. A practical example of this efficiency is the solution to a complex problem in communications network optimization where the solution time was reduced from weeks to days. His algorithm thus enables faster business and policy decisions. Karmarkar's algorithm has stimulated the development of several interior point methods, some of which are used in current implementations of linear program solvers.

Galois geometry

After working on the Interior Point Method, Karmarkar worked on a new architecture for supercomputing, based on concepts from finite geometry, especially projective geometry over finite fields.

Current investigations

Currently, he is synthesizing these concepts with some new ideas he calls sculpturing free space. This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work, including an extended abstract. This new paradigm was presented at on 16 July 2008, and at MIT on 25 July 2008. Some of his recent work is published at . He delivered a lecture on his on going work at IIT Bombay in September 2013. He gave a four-part series of lectures at FOCM 2014 titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.

Awards