CS Paper Radar

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

Minbo Gao, Kun He, Tao Jiang

cs.DS ·submitted 2026-11-06 11:31 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Fine-Grained Complexity Across the Computational Phase Transition

cs.CC cs.DSmath.PR ·2026-11-02 ·Zhe Ju, Jingcheng Liu, Yitong Yin
theory similarity 0.65
Abstract

How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.

0.51

Lowered crossover points of Anthropic's subexponential 3-SAT algorithm

cs.CC cs.DS ·2026-10-30 ·Ruhollah Majdoddin
theorycode/data similarity 0.65
Abstract · 56 pages. Scripts: https://github.com/Majdoddin/anthropic-3sat-crossover

The October 2026 refutations of the Exponential Time Hypothesis count satisfying assignments in time $2^{o(n)}$, but an asymptotic bound does not say from which input size, the crossover point, they beat the best known algorithms. We make the #3-SAT recursion of Anthropic's algorithm explicit and lower its crossover points, computed from the main term of the proved bound, by proved changes. For the bound in the number $m$ of clauses, at clause density one, the crossover point drops to about $2^{420}$ clauses from $2^{33858}$; for general 3-SAT, in the number $n$ of variables, our estimate drops to $2^{8.6\cdot10^9}$ variables from $2^{2.2\cdot10^{12}}$. With integer tables the recursion counts, for every $j$, the assignments satisfying exactly $j$ clauses in time $2^{O(m/\sqrt{\log m})}$. We observe that this refutes the Sparse Max-3-SAT Hypothesis of Alman and Vassilevska Williams, which also follows from either refutation by the reduction of Impagliazzo, Paturi and Zane, and we lower the crossover point of this computation to about $2^{1016}$ clauses from $2^{68364}$. The distance is structural: we define a rewrite-and-merge class that contains the recursion and all our constructions, and prove that in the main-term model no grid algorithm in it can gain for general 3-SAT below about $2^{6000}$ variables. For two balanced homogeneous merges we prove with quantum functionals an exponent of at least $(\log_2K)^{-3}$ per edge bit, which excludes running times $2^{n^{1-c}}$. Independently of SAT, we formalise the algorithm as a model of computation, Signed Network Sums, which contains rank-one methods and contraction trees. On the complete graph with four nodes, one-level constructions contract the network in $N^{23/6}$ if $ω=2$ and in about $N^{3.93}$ on the current (preprint) matrix-multiplication curve, below the bound $N^4$ of every rank-one method or contraction tree.

0.63

Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds

cs.DS ·2026-10-11 ·Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao
similarity 0.65
Abstract

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

0.29

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.63
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

ETH is Dead, Long Live SH

cs.CC ·2026-11-02 ·MIT Hardness Group, Josh Brunner, Erik D. Demaine, Fabian Frei, Timothy Gomez +3 more
theory similarity 0.62
Abstract · 13 pages, 1 table

Impagliazzo and Paturi's 1999 Exponential Time Hypothesis (ETH) is false, but Stearns and Hunt's 1990 Satisfiability Hypothesis (SH) remains plausible. We prove that SH is equivalent to the recently proposed Weak ETH which rules out $O(2^{n^{1-\varepsilon}})L^{O(1)}$-time 3SAT algorithms for every constant $\varepsilon>0$, where $L$ is the input length. We show that SH (or Weak ETH) preserves the typical process for lower bounds: a polynomial-time reduction from a 3SAT formula of size $s=Θ(n+m)$ to an instance of size $N\le s^{b+o(1)}$, for fixed blowup exponent $b>0$, rules out $O(2^{N^{1/b-\varepsilon}})$-time algorithms for every constant $\varepsilon>0$. By comparison, for an $N=O(s^b)$ blowup, ETH would have ruled out $2^{o(N^{1/b})}$-time algorithms. The framework also yields parameterized lower bounds ruling out running times of the form $O(2^{k^{1/b-\varepsilon}})L^{O(1)}$. We also prove equivalence of the analogous counting hypotheses, #SH and Weak #ETH, and that they rule out $O(2^{(n+m)^{1-\varepsilon}})$-time algorithms for #2SAT for every constant $\varepsilon>0$.

0.29

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

cs.DS ·2026-11-01 ·Yang Cao, Haoran Qi, Hanzhi Wang
similarity 0.62
Abstract

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(mn^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has remained the fastest for every $k\geq3$ for over four decades, even when the paths must be shortest. We break this bound for every $k\geq3$ with randomized algorithms running in expected $O_k(m+n^{k-3+ω+\varepsilon})$ time for every $\varepsilon>0$, where $ω<2.372$ is the matrix multiplication exponent; this is $O_k(m+n^{k-0.62})$. For two disjoint shortest paths, we find the paths as fast as we detect them: in expected linear time on DAGs and on undirected graphs with polynomially bounded integer weights, and in expected $O(\min\{mn,n^{ω+\varepsilon}\})$ time on directed graphs whose cycles have positive weight, which on dense graphs is $o(mn)$ even for detection. All algorithms evaluate a polynomial whose monomials are the solutions: a new first-collision circuit speeds up the evaluation in DAGs, and a correlated extraction step at cuts crossed once by every path finds a solution at the cost of a constant number of evaluations.

0.20

Structural Corrections to the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-31 ·Ijay Narang, Will Perkins
hot direction similarity 0.62
Abstract

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.

0.45

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.62
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27