Location:
Faculty Hall
Robert Bosch Center Distinguished Lecture Series
Title: Continuum Computing — The Next Step in Theory of Computing, Speaker: Dr. Narendra Karmarkar, Distinguished Visiting Professor, IIT Mandi and IISc Bangalore, Date: October 28 2016, Time: 4-5pm, High Tea after the talk, Venue: Faculty Hall, IISc
Abstract
One of the goals of any model of computation is to provide basic understanding of various computational problems to enable design of efficient machines and algorithms. The first major successful step in this direction is the concept of Turing machines. However, this model is not adequate for understanding the full power of algorithms that use the concept of the continuum in an essential way, such as the interior point methods, which are highly successful in solving NP-complete problems arising in engineering applications. Various lower bound or inapproximability results in the Turing model do not show any intrinsic limitations of computing but only represent limitations of a particular framework. Careful study of the work of early pioneers Turing, Von Neumann and Godel shows that they were all aware of these limitations. A broader view of theory of computing has therefore become necessary to understand the new algorithms and design of next generation of computers. Advanced continuum based algorithms have applications in many areas of Engineering Optimization, Computational Physics and areas of Computer Science such as Artificial Intelligence.
Our research program in these algorithms has multiple components new mathematical or algorithmic concepts, a software framework aimed at providing an actionable Knowledge Representation System for their implementation, theory and computational experiments.
While Quantum Computing is based different physical principles, continuum computing is based on new mathematical concepts to go beyond current limitations of computing. Unlike quantum computing which loses its advantages if simulated on conventional machines, the continuum computing retains enough of its advantage even in simulation on current machines as an intrim step.
The seminar is aimed at giving a simplified introduction for students interested in undertaking projects in this area.
Biodata: Dr. Karmarkar received his B.Tech in Electrical Engineering from IIT Bombay in 1978, M.S. from the California Institute of Technology[3] and Ph.D. in Computer Science from the University of California, Berkeley in 1983 under the supervision of Richard M. Karp.[4]
He invented a polynomial algorithm for linear programming also known as the 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. Karmarkar was a professor at the Tata Institute of Fundamental Research in Mumbai.
Karmarkar has received a number of awards:
- Paris Kanellakis Award, 2000 given by The Association for Computing Machinery 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 in Discrete Mathematics given jointly by the American Mathematical Society & Mathematical Programming Society (1988)
- Fellow of Bell Laboratories (1987)
- Texas Instruments Founders’ Prize (1986)
- Marconi International Young Scientist Award (1985)
- American Academy of Achievement award, 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)
