ECCC-Report TR15-007https://eccc.weizmann.ac.il/report/2015/007Comments and Revisions published for TR15-007en-usFri, 09 Jan 2015 21:43:19 +0200
Paper TR15-007
| Combinatorial Optimization Algorithms via Polymorphisms |
Jonah Brown-Cohen,
Prasad Raghavendra
https://eccc.weizmann.ac.il/report/2015/007An 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.Fri, 09 Jan 2015 21:43:19 +0200https://eccc.weizmann.ac.il/report/2015/007