FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 13, 18:05 ~ 18:55 - Room B11
Towards a Broader View of Theory of Computing -- Part 2
Narendra Karmarkar
Indian Institute of Technology, Bombay, India - narendrakarmarkar@yahoo.com
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 benefitted from many pre-established ideas from classical mathematics, but non-convex problems require new concepts. This three part series outlines some of these concepts -- 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.
Topics for part 2 - In this session, 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 covered in part 3.
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.