Polymorphisms and Polynomial-time algorithms.
Speaker: Prasad Raghavendra, UC Berkeley
Date: Tuesday, November 6 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-124
Host: Costis Daskalakis, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Why is 2-SAT solvable in polynomial time but 3-SAT NP-complete? Why is MaxCut approximable to a ratio of 0.878, but unique-games hard to approximate any better? Why is minimum s-t cut polytime solvable, but 3-way cut approximable to a 12/11 factor? Why is submodular minimization easy in general? In all these cases, the existence of polymorphisms seems to characterize the existence of polynomial time algorithms.
Roughly speaking, a polymorphism is an operation to combine different solutions to a problem, that preserves the constraints or the objective value of the problem. For the class of exact constraint satisfaction problems (CSP), the algebraic dichotomy conjecture asserts that a CSP is polytime solvable if and only if the CSP admits non-trivial polymorphisms. The algebraic approach to exact CSPs has been highly successful in characterizing large classes of exact CSPs, including all CSPs over domain size up to 4. More recently, an analogous theory for approximation of Max-CSPs was developed and shown to be equivalent to the well-known unique games conjecture. Thus polymorphisms seemingly characterize existence of polytime algorithms for CSPs, both for exact CSPs and approximation versions.
In this work, we initiate the study of polymorphisms to classes of problems beyond CSPs. Specifically, we show the following result:
1) Suppose we are given access to a function F in the value oracle model, along with an operation/polymorphism on the domain that never increases the value of F. Submodular minimization is a well-known example of this nature, with the operation being 2-bit AND and 2-bit OR. We show that under certaing restrictions on the operation/polymorphism, the function F can be minimized in polynomial time. This shows that the tractability of submodular minimization in the value-oracle model is a special case of a more general phenomenon.
See other events that are part of Theory Colloquium 2012/2013
See other events happening in November 2012
