Login
Talks & Seminars
Title: Advanced Algorithmic Approach to Optimization
Dr. Narendra Karmarkar, Scientific Adviser in HPC to the Government of India
Date & Time: September 26, 2013 15:00
Venue: Lecture Hall, B Block, 03rd Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
Beginning with the projectively invariant algorithm for linear programming, interior point methods have led to advanced algorithms applicable to a broad range of computational problems. 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 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 bound or inapproximability results 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 the limitations. A broader view of theory of computing has become necessary to understand the new algorithms. 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. The first seminar( in EE dept.) in this two part series gives a broad overview and outline of some new concepts to overcome limitations of convexity is in the second part (in CS Dept.) • Gradation of connected sets based on ( k, l )-connectivity. In this scheme, convex sets are (1, 1)-connected and form the bottommost layer. Sets with higher connectivity indices play an important role in advanced algorithms. • Concepts of degree and algebraicity relative to a metric or an affine connection, in a curved space. If all covariant derivatives of a function, except for a finite number vanish, the function behaves like a polynomial in the curved space. Zero set of the function can be regarded as a “relatively algebraic” set w.r.t. the affine connection. We develop methods for defining a curved space adapted to the problem data so that the function to be optimized becomes relatively algebraic with small degree.
Speaker Profile:
Narendra Karmarkar received his BTech in Electrical Engineering from IIT Bombay in 1978, MS from the California Institute of Technology and PhD in Computer Science from UC Berkeley. He is the inventor of 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 this result in 1984 while working for Bell Laboratories in New Jersey. Narendra was a Professor at TIFR Mumbai. He has received numerous awards including Paris Kanellakis Award in 2000 from ACM, and Fulkerson Prize in 1988 from AMS and Mathematical Programming Society. He is also a Distinguished Alumnus of UC Berkeley (1993) and IIT Bombay (1996). He is currently working on a new architecture for supercomputing. Some of the ideas are published in IEEE journals and Fab5 conference organized by MIT center for bits and atoms.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback