CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of th…