CSPs with global modular constraints: algorithms and hardness via polynomial representations

DOI10.1145/3313276.3316401zbMath1433.68270arXiv1902.04740OpenAlexW2913322957MaRDI QIDQ5212801

Sivakanth Gopi, Joshua Brakensiek, Venkatesan Guruswami

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.04740

zbMATH Keywords

polynomial representationsconstraint satisfaction problemssubmodular minimizationexponential time hypothesis (ETH)modular constraintsmatching vector families

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items

Turán numbers of sunflowers, Constraint satisfaction problem: what makes the problem easy, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, CNF satisfiability in a subspace and related problems