CSPs with global modular constraints: algorithms and hardness via polynomial representations
From MaRDI portal
Publication:5212801
DOI10.1145/3313276.3316401zbMATH Open1433.68270arXiv1902.04740OpenAlexW2913322957MaRDI QIDQ5212801
Author name not available (Why is that?)
Publication date: 30 January 2020
Published in: (Search for Journal in Brave)
Abstract: 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 reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod M. The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod M, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by N"agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kind of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems, and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite M.
Full work available at URL: https://arxiv.org/abs/1902.04740
No records found.
No records found.
This page was built for publication: CSPs with global modular constraints: algorithms and hardness via polynomial representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212801)
