College of Engineering Seminar - Dr. Narendra Karmarkar

Event Date: April 23, 2013
Time: 4:30 p.m.
Location: Krannert Auditorium, WL campus
"Advanced Algorithmic Approach to Optimization" presented by Dr. Narendra Karmarkar.

Beginning with the projectively invariant algorithm for linear programming, interior point methods have led to advanced algorithms that are applicable to a broad range of problems in Operations Research. These algorithms use the concept of the continuum in an essential way. As shown by Godel and Cohen, the continuum hypothesis is beyond the reasoning power of the axioms of set theory. Similarly, the Turing machine model was expressly designed for dealing with countable sets, and is inadequate for understanding the full power of algorithms based on the continuum concept. Various lower bounds and inapproximability results that have been reported do not show "intrinsic" limitations of computing but rather represent limitations of particular frameworks in which the results were derived. Careful study of the work of early pioneers - Turing, Von Neumann and Godel - shows that they were aware of the limitations of the discrete model of computation. Since the continuum based algorithms are yielding new insights into finer structure differentiating, easy and hard problems (not available within the Turing machine model), a broader view of theory of cmputing has become necessary.

Our research program to deelop such a new breed of algorithms based on the continuum concept has three components - new mathematical and algorithmic concepts that provide the building blocks of the new theory, a software framework aimed at providing an "actionable" Knowledge Representation System for implementing and composing the building blocks into complete solvers, and computational experiments to assess the computational difficulty of various abstract as well as real world problem classes.

The description of our ongoing research program will be presented in two seminars. The first seminar (Apr. 23), aimed at a general audience, will present a broad overview of the research program and the motivation for focusing on the continuum model. The second seminar (Apr. 25), aimed at the community of researchers engaged in algorithm design, will delve into deeper aspects of computation including some new concepts to overcome the limitations of convexity. The second seminar assumes some familiarity with concepts from differential geometry, algebraic geometry and mathematical hysics, particularly General Relativity.