Login
Talks & Seminars
Title: Towards a Broader View of Theory of Computing (Part 1)
Dr. Narendra Karmarkar, Government of India
Date & Time: November 27, 2014 15:30
Venue: F. C. Kohli Auditorium, B Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
Beginning with the projectively invariant method for linear programming, interior point methods have led to powerful algorithms for many difficult computing problems, in combinatorial optimization, logic, number theory and non-convex optimization. Algorithms for convex optimization benefited from many pre-established ideas from classical mathematics, but non-convex problems require new concepts, such as, computational models based on the concept of the continuum, algorithms invariant with respect to transformations on co-ordinate representation-projective, bi-rational, and bi-holomorphic transformations, extended proof systems for more efficient certificates of optimality, extensions of Grassmann’s extension theory, efficient evaluation methods for the effect of exponential number of constraints, theory of connected sets based on graded connectivity, theory of curved spaces adapted to the problem data, and concept of “relatively” algebraic sets in curved space. In this talk series, we first briefly review the continuum computing model. We show how algorithms based on continuum computing can obtain exponential speed-up over those based on Turing machines by considering concrete examples of finding maximum independent set in a graph and the satisfiability problem. We review the concept of graph minors based on parity-respecting homeomorphisms. Although there can be exponential number of subgraphs homeomorphic to a given minor, we show how their combined effect can be computed in polynomial number of operations in the continuum approach. We extend the concept of graph minors to sub-formulas in a satisfiability problem. As shown by Chvátal and Szemerédi, almost all instances of the problem for certain range of parameter require exponential time for resolution. We identify sub-formulas, which we call “mobius cycles”, as the culprits causing exponential behavior, and show that their combined effect can be computed in polynomial number of operations in the continuum approach. The method can be thought of as generalizing the generating functions used in enumerative combinatorics to continuum based algorithms. Objective function for these problems is treated by non-convex optimization methods. Computational results are obtained by approximate cross-simulation on the standard model of computation. Ability of algebroid functions to efficiently encode and process information regarding exponential number of combinatorial substructures should not come as a surprise, given that the most famous meromorphic function -- the Riemann Zeta function -- is able to carry information regarding the infinite sequence of primes. Time permitting, more topics from the list mentioned at the outset will be covered. All these topics form the content of the talks that are to be delivered at FOCM 2014.
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