Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-007 | 8th January 2015 18:02

Combinatorial Optimization Algorithms via Polymorphisms


Authors: Jonah Brown-Cohen, Prasad Raghavendra
Publication: 9th January 2015 21:43
Downloads: 1700


An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP $\Lambda$ is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to $\Lambda$ to create new ones. In an entirely separate line of work, the unique games conjecture yields a characterization of approximability of Max-CSPs. Surprisingly, this characterization for Max-CSPs can also be reformulated in the language of polymorphisms.
In this work, we study whether existence of non-trivial polymorphisms implies tractability beyond the realm of constraint satisfaction problems, namely in the value-oracle model. Specifically, given a function f in the value-oracle model along with an appropriate operation that never increases the value of f , we design algorithms to minimize f . In particular, we design a randomized algorithm to minimize a function f that admits a fractional polymorphism which is measure preserving and has a transitive symmetry.
We also reinterpret known results on MaxCSPs and thereby reformulate the unique games conjecture as a characterization of approximability of max-CSPs in terms of their approximate polymorphisms.

ISSN 1433-8092 | Imprint