Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JONAH BROWN-COHEN:
All reports by Author Jonah Brown-Cohen:

TR15-007 | 8th January 2015
Jonah Brown-Cohen, Prasad Raghavendra

Combinatorial Optimization Algorithms via Polymorphisms

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 ... more >>>




ISSN 1433-8092 | Imprint