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.

Thu 5 NovDiscrete Mathematics
The gist
Figuring out whether certain kinds of equations with whole number solutions can be solved is surprisingly tricky. This paper shows that even when the equations are arranged in a very simple pattern—a cycle where each equation and variable only connects twice—the problem is still very hard to solve. The authors prove this remains true under strict limitations on the numbers used and how the equations are formed. They also explain that because of this, some hoped-for shortcuts or efficient methods for solving these problems are unlikely to exist.
Open → 2611.08304v1

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.

Wed 4 NovData Structures and AlgorithmsDiscrete Mathematics
The gist
The paper studies how solutions to a complex logical puzzle called random k-SAT are connected and change as you adjust the number of rules. The authors show that up to a certain point, you can move between solutions by flipping one variable at a time in a way that always keeps the puzzle solvable. They identify precise mathematical thresholds where the solution space changes structure—from connected, to clustered, to rigid where flipping variables becomes hard. This deepens understanding of the puzzle’s structure and transitions as its difficulty increases.
Open → 2611.05981v1

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.

Tue 3 NovComputational ComplexityData Structures and Algorithms
The gist
This paper studies a kind of mathematical graph used to represent partial solutions in complex logical puzzles involving many variables. The authors found new ways to measure how closely these partial solutions resemble a perfect complete solution, even when the data overlaps or repeats unpredictably. Their results improve previous bounds on how hard it is to find truly sound solutions under these conditions. They also provide a related result showing stability properties for sets of partial solutions with missing or multiple answers. However, the work does not establish new hardness results for computational problems.
Open → 2611.04457v1

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.

Tue 29 SeptData Structures and Algorithms
The gist
Constraint satisfaction problems (CSPs) involve finding solutions that satisfy many rules or constraints. The paper studies two types of random CSPs: ones that are usually unsolvable and ones designed to have a hidden solution. The authors show that known algorithms for these problems actually produce solutions with a certificate proving the solution is nearly the best possible. They also design new algorithms that handle cases where some constraints have been tampered with, still ensuring nearly optimal and verifiable solutions.
Open → 2609.38367v1

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.

Wed 23 SeptLogic in Computer Science
The gist
The problem is to color a chessboard so no two squares in the same row, column, or diagonal have the same color, using the fewest colors possible. The authors studied over a thousand ways to set up this problem for computer solvers, examining how different rules and hints affect solving speed. They found that the choices for breaking symmetrical solutions, adding special clues called clique hints, and strict rules assigning colors to squares have the biggest impact. They also showed some hints work well beyond the specific method Knuth originally suggested.
Open → 2609.27674v1