Papers for
constraint solver developers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Integer feasibility remains hard with simple cycle structures
Hardness of integer linear feasibility with cyclic support
Abstract: We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.
Random k-sat solutions connect by single flips below key density thresholds
Single-Variable Connectivity in Random $k$-SAT
Abstract: We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity. $\textbf{Single-variable connectivity up to reconstruction.}$ At clause densities up to \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*-o_k(1)\bigr),\] a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using $O_k(n)$ single-variable flips that preserve satisfiability. Here $γ_*\approx0.871$ arises from a refined tree-reconstruction analysis. $\textbf{Settling the reconstruction threshold.}$ Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*+o_k(1)\bigr),\] below the classical cavity prediction with constant term $1+O(\ln\ln k/\ln k)$. $\textbf{Shattering before rigidity.}$ We locate the looseness--rigidity transition at a higher density, matching the classical cavity prediction for clustering: \[\frac{2^k}{k} \left(\ln k+\ln\ln k+1+Θ\left(\frac{\ln\ln k}{\ln k}\right)\right).\] Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.
Soundness bounds for multi-answer birthday graphs in constraint problems
Entropy-Weighted Soundness for Multi-Answer Birthday Graphs
Abstract: The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.
Certifiable near-optimal solutions unify search and refutation in random csp problems
Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs
Abstract: A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.
Comparing thousands of chessboard colorings reveals key solver tricks
Coloring Queens with Thousands of Encodings
Abstract: In The Art of Computer Programming, Knuth benchmarked 10 encoding techniques for computing the chromatic number of the queen's graph: the minimum number of colors needed to color the squares of an $n \times n$ chessboard so that no two squares sharing a row, column, or diagonal receive the same color. In this paper, we extend his analysis much further by comparing thousands of encodings for the same problem, which allows us to identify additional factors that are important for solver performance. We obtain 1584 encodings for this problem by varying (a) the constraints that encode which color is assigned to each cell, (b) the constraints that forbid the same color appearing in a row, column, or diagonal line, and (c) the symmetry-breaking constraints. We find that the three most impactful encoding factors are (i) the choice of symmetry-breaking constraints, (ii) enabling so-called clique hints, and (iii) enforcing that each cell is assigned exactly one color through blocked clauses. Furthermore, while Knuth proposed clique hints as an advantage of the order encoding, we show in fact that they can be effectively employed for the one-hot encoding as well.