Papers for

constraint satisfaction engineers

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.

Algorithms face sharp limits on solving logic puzzles efficiently

Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF

Abstract: We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

Fri 6 NovData Structures and Algorithms
The gist
Many computer algorithms try to solve logic puzzles called 3-CNF formulas by flipping variables or resampling groups of variables. The authors found that these algorithms work quickly when each variable appears only a few times, but suddenly slow down drastically when variables appear more often. Surprisingly, this slowdown happens before the problem becomes truly hard to solve. They also show that the two popular algorithms can behave very differently on the same puzzle, with one solving it quickly while the other takes exponentially longer, and vice versa.
Open → 2611.09335v1