Narendra Krishna Karmarkar (born Circa 1956) 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 Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...

New Jersey New Jersey is a state in the Mid-Atlantic and Northeastern regions of the United States. It is bordered on the north and east by the state of New York; on the east, southeast, and south by the Atlantic Ocean; on the west by the Delaware ...

Biography

Karmarkar received his

B.Tech A Bachelor of Technology (Latin ''Baccalaureus Technologiae'', commonly abbreviated as B.Tech. or BTech; with honours as B.Tech. (Hons.)) is an undergraduate academic degree conferred after the completion of a three to five-year program of stud ...

in Electrical Engineering from

IIT Bombay The Indian Institute of Technology Bombay (IIT Bombay or IITB) is a public research university and technical institute in Powai, Mumbai, Maharashtra, India. It is considered as one of the best engineering universities in India and is top rank ...

in 1978, MS from the

California Institute of Technology The California Institute of Technology (branded as Caltech or CIT)The university itself only spells its short form as "Caltech"; the institution considers other spellings such a"Cal Tech" and "CalTech" incorrect. The institute is also occasional ...

in 1979, and PhD in Computer Science from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

in 1983 under the supervision of Richard M. Karp. Karmarkar was a post-doctoral research fellow at IBM research (1983), Member of Technical Staff and fellow at Mathematical Sciences Research Center, AT&T Bell Laboratories (1983-1998), professor of mathematics at M.I.T. (1991), at Institute for Advanced study, Princeton (1996), and Homi Bhabha Chair Professor at the

Tata Institute of Fundamental Research Tata Institute of Fundamental Research (TIFR) is a public deemed research university located in Mumbai, India that is dedicated to basic research in mathematics and the sciences. It is a Deemed University and works under the umbrella of the ...

Mumbai Mumbai (, ; also known as Bombay — List of renamed Indian cities and states#Maharashtra, the official name until 1995) is the capital city of the Indian States and union territories of India, state of Maharashtra and the ''de facto'' fin ...

from 1998 to 2005. He was the scientific advisor to the chairman of the TATA group (2006-2007). During this time, he was funded by Ratan Tata to scale-up the supercomputer he had designed and prototyped at TIFR. The scaled up model ranked ahead of supercomputer in Japan at that time and achieved the best ranking India ever achieved in supercomputing. He was the founding director of Computational Research labs in Pune where the scaling up work was performed. He continues to work on his 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 method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...

s, some of which are used in current implementations of linear program solvers.

Galois geometry

After working on the

Interior Point Method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...

, Karmarkar worked on a new

architecture Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and constructing building ...

for supercomputing, based on concepts from

finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marke ...

, especially

projective geometry In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, ...

over

finite fields In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

Current investigations

Currently, he is synthesizing these concepts with some new ideas he calls ''sculpturing free space'' (a non-linear analogue of what has popularly been described as ''folding the perfect corner''). 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 a
IVNC, Poland
on 16 July 2008, and at

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...

on 25 July 2008. Some of his recent work is published a
ieeexplore
http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009 He delivered a lecture on his ongoing work at

in September 2013. He gave a four-part series of lectures at FOCM 2014 (Foundations of Computational Mathematics) titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.

Awards

* The Association for Computing Machinery awarded him the prestigious

Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...

in 2000 for his work on polynomial time interior point methods for linear programming for "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". * Srinivasa Ramanujan Birth Centenary Award for 1999, presented by the Prime Minister of India. * Distinguished Alumnus Award, Indian Institute of Technology, Bombay, 1996 * Distinguished Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993) *

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

in Discrete Mathematics given jointly by the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

Mathematical Programming Society The Mathematical Optimization Society (MOS), known as the Mathematical Programming Society until 2010,American Academy of Achievement The American Academy of Achievement, colloquially known as the Academy of Achievement, is a non-profit educational organization that recognizes some of the highest achieving individuals in diverse fields and gives them the opportunity to meet ...

, presented by former U.S. president (1985)
Frederick W. Lanchester Prize
of the Operations Research Society of America for the Best Published Contributions to Operations Research (1984) * President of India gold medal, I.I.T. Bombay (1978)

References

External links

Distinguished Alumnus 1996
IIT Bombay

IIT Bombay Heritage Fund

in Scilab {{DEFAULTSORT:Karmarkar, Narendra 1957 births Living people Theoretical computer scientists Numerical analysts 20th-century Indian mathematicians 21st-century Indian mathematicians Indian computer scientists American computer scientists Scientists at Bell Labs University of California, Berkeley alumni IIT Bombay alumni California Institute of Technology alumni Indian emigrants to the United States American operations researchers Indian operations researchers American academics of Indian descent People from Gwalior