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

@article{Brakensiek2019CSPsWG, title={CSPs with global modular constraints: algorithms and hardness via polynomial representations}, author={Joshua Brakensiek and Sivakanth Gopi and Venkatesan Guruswami}, journal={Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing}, year={2019} }

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 the modulus M. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the ETH). Our study… Expand

#### 2 Citations

CNF Satisfiability in a Subspace and Related Problems

- Computer Science
- Electron. Colloquium Comput. Complex.
- 2021

It is proved that the optimization version Max-2-SUB-SAT is NP-hard to approximate better than the trivial 3/4 ratio even on satisfiable instances, and fast exponential algorithms which give non-trivial savings over brute-force algorithms are investigated which achieves polynomial space in contrast to the algebraic approach that uses exponential space. Expand

Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

- Mathematics, Computer Science
- APPROX-RANDOM
- 2019

The hardness for Max-2-Sat applies to monotone Max- 2-Sat instances, meaning that it is proved that tight inapproximability for the Max-k-Vertex-Cover problem is obtained. Expand

#### References

SHOWING 1-10 OF 45 REFERENCES

Submodular Minimization Under Congruency Constraints

- Computer Science, Mathematics
- SODA
- 2018

It is shown that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. Expand

Classifying the Complexity of Constraints Using Finite Algebras

- Mathematics, Computer Science
- SIAM J. Comput.
- 2005

It is shown that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra is explored. Expand

A Proof of CSP Dichotomy Conjecture

- Computer Science, Mathematics
- 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
- 2017

An algorithm is presented that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. Expand

Which Problems Have Strongly Exponential Complexity

- Mathematics
- 2001

For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these… Expand

Complexity of Approximating CSP with Balance / Hard Constraints

- Computer Science, Mathematics
- Theory of Computing Systems
- 2015

It is proved the inapproximability of these problems with balance or hard constraints, showing that each variant changes the nature of the problems significantly (in different ways). Expand

A lower bound on the mod 6 degree of the OR function

- Mathematics, Computer Science
- computational complexity
- 1998

Here, a lower bound of $\Omega (\log n)$ is shown when m is a product of two primes and $\log n1/(r-1)})$ in general is shown, which is the best known for any function of low communication complexity and any modulus not a prime power. Expand

Linear Systems over Composite Moduli

- Computer Science, Materials Science
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science
- 2009

The first exponential lower bound on the size of depth-three circuits of type having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized MOD_m gates atThe base is derived, computing the function MOD_q. Expand

A dichotomy theorem for constraint satisfaction problems on a 3-element set

- Mathematics, Computer Science
- JACM
- 2006

Every subproblem of the CSP is either tractable or NP-complete, and the criterion separating them is that conjectured in Bulatov et al. Expand

The complexity of satisfiability problems

- Computer Science, Mathematics
- STOC
- 1978

An infinite class of satisfiability problems is considered which contains these two particular problems as special cases, and it is shown that every member of this class is either polynomial-time decidable or NP-complete. Expand

Constructing Ramsey graphs from Boolean function representations

- Computer Science, Mathematics
- 21st Annual IEEE Conference on Computational Complexity (CCC'06)
- 2006

The barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations, and it is shown that better bounds cannot be obtained using symmetric polynomials. Expand