A new line of attack on the dichotomy conjecture

DOI10.1145/1536414.1536512zbMath1304.68076OpenAlexW1975452925MaRDI QIDQ5172770

Gábor Kun

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/44212/2/TR09_059_u.pdf

zbMATH Keywords

computational complexityFourier analysisterm operationsdichotomyconstraint satisfaction problemsNP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (6)

Tractability in constraint satisfaction problems: a survey ⋮ In praise of homomorphisms ⋮ \(H\)-colorings of dense hypergraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Unnamed Item ⋮ A quasi-Mal'cev condition with unexpected application.

This page was built for publication: A new line of attack on the dichotomy conjecture