\section{Preliminaries}\label{sec:prelim}

This section fixes the model, states the new algorithms, builds the computational engine that
the rest of the paper uses, and lists the hypotheses that survive.

\subsection{Notation and the learning model}\label{sec:model}

We write $\log$ for $\log_2$ and $[n]$ for $\{1,\dots,n\}$. For $w\in\{0,1\}^N$ and $R\subseteq[N]$,
the string $w|_R$ is the restriction of $w$ to $R$. A \emph{clause} is a nonempty set of literals, and
its \emph{width} is its size. A \emph{CNF} is a finite set of clauses, and a \emph{$k$-CNF} has only
clauses of width at most $k$. The \emph{length} $L$ of a CNF is its number of literal occurrences,
$L=\sum_C|C|$. For a CNF $F$ on declared variables $z_1,\dots,z_n$, the number $\#F$ counts the
satisfying assignments in $\{0,1\}^n$, and $\SAT(F)$ is the set of these assignments. We measure time
in the word-RAM model, and ``polynomial'' means polynomial in the input length.

A \emph{sample} is a sequence $S=((x_1,y_1),\dots,(x_m,y_m))$ of labeled examples. For a class
$\cH=\{h_w:w\in\{0,1\}^N\}$, the \emph{version space} of $S$ is
$\VS(S)=\{w:h_w(x_i)=y_i\text{ for all }i\}$, and the \emph{empirical error} of $w$ is
$\err_S(w)=|\{i:h_w(x_i)\ne y_i\}|/m$. The \emph{error profile} of $S$ is the generating polynomial of
the error counts,
\[
E_S(V)=\sum_{w\in\{0,1\}^N}V^{\,m\cdot\err_S(w)}=\sum_{j=0}^{m}c_jV^j ,
\]
so the coefficient $c_j$ is the number of descriptions that misclassify exactly $j$ examples. For a
distribution $\cD$ on labeled examples, $\err_\cD(w)=\Pr_{(x,y)\sim\cD}[h_w(x)\ne y]$ and
$\opt=\min_w\err_\cD(w)$. A \emph{proper} learner outputs a description $w$. It is an
\emph{$(\eps,\delta)$-agnostic learner} if $\err_\cD(w)\le\opt+\eps$ with probability at least
$1-\delta$, and an \emph{$(\eps,\delta)$-PAC learner} if this holds whenever $\opt=0$. We use three
standard sample sizes.

\begin{fact}[Sample sizes; see~\cite{BEHW87,BEHW89,SSBD14}]\label[fact]{fact:samples}
Let $\cH$ have description length $N$ and VC dimension $d\ge1$. There are absolute constants
$C_0,C_B\ge1$ such that the following hold with probability at least $1-\delta$ over a sample of $m$
independent examples from $\cD$.
\begin{enumerate}[label=(\alph*)]
\item \emph{Occam.} If $\opt=0$ and $m\ge\mOcc:=(N\ln2+\ln(1/\delta))/\eps$, then every
$w\in\VS(S)$ has $\err_\cD(w)\le\eps$.
\item \emph{Realizable VC bound.} If $\opt=0$ and $m\ge\mVC:=C_B(d\log(2/\eps)+\log(2/\delta))/\eps$,
then every $w\in\VS(S)$ has $\err_\cD(w)\le\eps$.
\item \emph{Uniform convergence.} If $m\ge\mUC:=C_0(d+\ln(1/\delta))/\eps^2$, then every $w$ has
$|\err_S(w)-\err_\cD(w)|\le\eps/2$. Thus every minimizer of $\err_S$ is $\eps$-optimal.
\end{enumerate}
\end{fact}

\subsection{Local hypothesis classes}\label{sec:local}

\begin{definition}[Local class]\label[definition]{def:local}
Let $N,\kappa\ge1$. A \emph{$\kappa$-local class} $\cH$ on a domain $\cX$ assigns to every $x\in\cX$ a
set $R(x)\subseteq[N]$ with $|R(x)|\le\kappa$ and a predicate $f_x:\{0,1\}^{R(x)}\to\{0,1\}$, both
computable in time polynomial in $N$ and the length of $x$. A \emph{description} $w\in\{0,1\}^N$ defines
the hypothesis $h_w(x)=f_x(w|_{R(x)})$, and $\cH=\{h_w:w\in\{0,1\}^N\}$. We call $N$ the
\emph{description length} and $\kappa$ the \emph{locality}.
\end{definition}

Because $|\cH|\le2^N$, the VC dimension of a class with description length $N$ is at most $N$. The
following classes are local on sparse data. In each of them, $R(x)$ is determined by the support of
$x$, and a sign vector $\sigma\in\{\pm1\}^n$ is described by the bits $w_i=(1+\sigma_i)/2$.

\begin{example}[Models on sparse data]\label[example]{ex:local}
Let $\cX_k=\{x\in\{-1,0,1\}^n:|\supp(x)|\le k\}$.
\begin{enumerate}[label=(\alph*)]
\item \emph{Literal disjunctions} $\LD_k$ on $\cX_k$: $h_\sigma(x)=1$ if and only if $x_i=\sigma_i$ for
some $i\in\supp(x)$. Here $N=n$ and $\kappa=k$. A sample of positive examples is a $k$-CNF: the example
$x$ is the clause $\bigvee_{i\in\supp(x)}(\sigma_i=x_i)$.
\item \emph{Binarized perceptrons} $\BP_k$ on $\cX_k$: $h_\sigma(x)=\ind[\langle\sigma,x\rangle\ge0]$.
Here $N=n$ and $\kappa=k$.
\item \emph{$b$-bit linear threshold models} on $k$-sparse integer data, with weights in
$\{-2^{b-1},\dots,2^{b-1}-1\}$ and a fixed threshold. Here $N=bn$ and $\kappa=bk$.
\item \emph{Quantized embedding models.} Each token of a vocabulary $[n]$ has an embedding in
$\{0,1\}^b$. An input is a sequence of at most $k$ tokens, and the output is a fixed polynomial-time
function of their embeddings. Here $N=bn$ and $\kappa=bk$. Factorization machines with binary factors
are a special case.
\item \emph{Sparse parities}: $h_w(x)=\langle w,x\rangle\bmod 2$ on $\{x\in\{0,1\}^n:|x|\le k\}$. Here
$N=n$ and $\kappa=k$.
\item \emph{Two-layer binarized networks} with $r$ hidden units on $\cX_k$:
$h(x)=\ind[\sum_{j\le r}a_j\,\mathrm{sgn}(\langle u_j,x\rangle)\ge0]$ with $u_j\in\{\pm1\}^n$,
$a\in\{\pm1\}^r$ and $\mathrm{sgn}(0)=1$. Here $N=rn+r$ and $\kappa=rk+r$.
\end{enumerate}
\end{example}

\subsection{The new algorithms}\label{sec:imported}

We use the two refutations of ETH only through the following three statements. The first counts the
solutions of $k$-CNFs for every $k$. The second does so in polynomial space. The third contracts
sparse tensor networks over a truncated polynomial ring.

\begin{fact}[{\cite[Main Theorem and Corollary~11]{Cla26}}]\label[fact]{fact:claude}
There are an absolute constant $C_1$ and a deterministic algorithm with the following property. Given
a $k$-CNF, for any $k\ge1$, with $M\ge2$ clauses in which $n\ge4$ variables occur, the algorithm
computes the number of satisfying assignments of these $n$ variables in time at most
\[
\min\Bigl\{2^{C_1kM/\sqrt{\log M}},\ 2^{C_1k^2n\log\log n/\sqrt{\log n}}\Bigr\}.
\]
\end{fact}

\begin{fact}[{\cite[Theorem~1.1]{OAI26}}]\label[fact]{fact:oai}
For each fixed $k\ge2$ there is a deterministic algorithm that, given a $k$-CNF $F$ on $n\ge20$
declared variables with $M$ clauses, computes $\#F$ in $(n+M)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log
n})}$ bit operations and $(n+M)^{O_k(1)}$ bits of space.
\end{fact}

A \emph{Boolean tensor network} is a bipartite multigraph $G$ in which every edge carries one bit.
Every vertex $v$ has an ordered list $\partial v$ of incident edges and a \emph{tensor} $\psi_v$, which
assigns a ring element to each Boolean assignment of $\partial v$. The \emph{contraction} of $G$ is
$\sum_{x\in\{0,1\}^{E(G)}}\prod_v\psi_v(x|_{\partial v})$. For integers $P,\ell\ge1$ let
\[
\Ring_{P,\ell}=(\Z/2^{P}\Z)[V]/(V^{\ell}).
\]

\begin{fact}[{\cite[Theorem~D.1]{OAI26}}, specialized]\label[fact]{fact:contract}
For every polynomial $p$ there is a constant $c_p$ with the following property. Let $s\ge2$, and let
$G$ be a bipartite Boolean tensor network with at most $s$ edges, at most $s$ vertices, maximum degree
at most $\lceil s^{9/10}\rceil$, and tensor entries in $\Ring_{P,\ell}$ with $P,\ell\le s$. Let $|G|$
be the bit length of the description of $G$, and suppose that each entry can be computed from it in
time $p(s+|G|)$. Then the contraction of $G$ can be computed deterministically in
$(s+|G|)^{c_p}\cdot2^{c_p s/\sqrt{\log s}}$ bit operations and $(s+|G|)^{c_p}$ bits of space.
\end{fact}

Theorem~D.1 of~\cite{OAI26} allows $O(s)$ edges, polynomially many vertices and more expensive
entries; we use only the special case above. The bound of \cref{fact:claude} is checked in
Lean~\cite{Cla26}. The Lean formalization of~\cite{OAI26} certifies Theorem~1.1 with the weaker rate
$(\log\log n)^2/\sqrt{\log n}$ and does not cover Theorem~D.1~\cite{OAI26lean}. Every result in this paper
that uses these statements holds verbatim with any improved rate. If \#$k$-SAT on $n$ variables takes time $2^{\rho(k,n)\,n}$, then
every exponent $\kappa^2N\log\log N/\sqrt{\log N}$ below becomes $\rho(\kappa,N)\,N$. The same holds for
the rate $1/\sqrt{\log s}$ of \cref{fact:contract}.

\subsection{The engine: sparse sum-products and error profiles}\label{sec:engine}

A \emph{factor graph} $\Phi$ over a commutative ring $\Ring$ consists of $n$ Boolean variables and a
finite family $\cF$ of \emph{factors}. Each factor $f$ has a \emph{scope} $I_f\subseteq[n]$ and a
\emph{table} $\psi_f:\{0,1\}^{I_f}\to\Ring$. The \emph{partition function} of $\Phi$ is
\[
Z(\Phi)=\sum_{x\in\{0,1\}^n}\ \prod_{f\in\cF}\psi_f(x|_{I_f}).
\]
The \emph{arity} of $\Phi$ is $\max_f|I_f|$, its \emph{size} is $\|\Phi\|=\sum_f|I_f|$, and the
\emph{degree} of a variable is the number of scopes that contain it. We write $|\Phi|$ for the bit length of
the description of $\Phi$. The next theorem is the engine of
all our algorithms. It turns \cref{fact:contract} into a statement about factor graphs.

\begin{restatable}[Sparse sum-product]{theorem}{thmsumproduct}\label{thm:sumproduct}
Let $\Phi$ be a factor graph over $\Ring_{P,\ell}$ of arity at most $a$, whose table entries can be
computed in polynomial time. Let $s$ be an integer with $s\ge\max\{4\|\Phi\|,P,\ell,2\}$ and
$a\le s^{9/10}$. Then $Z(\Phi)$ can be computed deterministically in time
$\poly(s+|\Phi|)\cdot2^{O(s/\sqrt{\log s})}$ and space $\poly(s+|\Phi|)$. The constants depend only on
the polynomial that bounds the time to evaluate one table entry.
\end{restatable}

\begin{proof}[Proof sketch]
Factors with empty scope are constants, and we multiply them in at the end. Every other factor
becomes a vertex of a tensor network. Every variable becomes a tree of equality tensors of degree at
most~$3$, whose leaves are the occurrences of the variable. A subdivision of every edge makes the network
bipartite. The result has at most $4\|\Phi\|$ edges and vertices, maximum degree $\max\{a,3\}$, and the
same contraction up to a factor~$2$ for each variable in no scope. \Cref{fact:contract} then applies.
\Cref{app:engine} gives the details.
\end{proof}

We use two rings. In the \emph{counting ring} $\Ring_{P,1}=\Z/2^P\Z$, a partition function whose value
is a nonnegative integer below $2^P$ is computed exactly. In the \emph{profile ring} $\Ring_{P,\ell}$,
tables with entries in $\{1,V\}$ make $Z(\Phi)$ a generating function. If $\ell$ exceeds the number of
factors, the coefficient of $V^j$ counts the assignments that pick the entry $V$ in exactly $j$
factors. Theorem~D.1 of~\cite{OAI26} allows truncation orders $\ell>1$, and its proof uses them. With
entries in $\{1,V\}$, a truncation order larger than the number of factors records every value of a
sparse objective at once, and this turns counting into optimization. Counting assignments by their
weight goes back to Williams' algorithm for Max-2-CSP~\cite{Wil05}. The first use is the error profile of a
sample.

\begin{restatable}[Exact error profiles]{lemma}{lemprofile}\label[lemma]{lem:profile}
Let $\cH$ be $\kappa$-local with description length $N$, let $S$ be a sample of size $m$, and let
$s=\max\{4\kappa m,\,m+1,\,\kappa^2\}$. The error profile $E_S$ can be computed exactly and
deterministically in time $\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$. The same holds for the error profile
of the descriptions that extend any given partial assignment.
\end{restatable}

\begin{proof}[Proof sketch]
Only the set $R(S)=\bigcup_iR(x_i)$ of description bits matters, and $|R(S)|\le\kappa m$. Build a factor
graph on the variables $R(S)$ over $\Ring_{P,\ell}$ with $P=|R(S)|+1$ and $\ell=m+1$. Example $i$
becomes a factor with scope $R(x_i)$ and with table $1$ where $f_{x_i}$ agrees with $y_i$ and $V$ where it
does not. An assignment with $j$ errors contributes $V^j$, and $j\le m<\ell$, so nothing is truncated.
No coefficient exceeds $2^{|R(S)|}<2^P$. So the partition function is the profile of the restricted
descriptions, and $E_S$ is $2^{N-|R(S)|}$ times it. \Cref{thm:sumproduct} applies with this $s$
(\cref{app:engine}).
\end{proof}

\subsection{Hypotheses that survive}\label{sec:hyp}

The new algorithms need bounded clause width, or linear total size. The hypotheses below concern
the opposite regime, and the new algorithms do not contradict
\cref{hyp:cnfseth,hyp:sharpcnfseth,hyp:cnfeth,hyp:maxsat}. \Cref{cor:sparsemaxsat} refutes
\cref{hyp:sparsemaxsat}, and \cref{hyp:leneth} is false for $C<1/2$ and open for $C\ge1/2$. We state all
hypotheses for randomized algorithms with error probability at most $1/3$.

\begin{hypothesis}[CNF-SETH]\label[hypothesis]{hyp:cnfseth}
For every $\gamma>0$ there is $c>0$ such that satisfiability of CNF formulas with $n$ variables and at
most $n^c$ clauses, of arbitrary width, cannot be decided in time $O(2^{(1-\gamma)n})$.
\end{hypothesis}

\begin{hypothesis}[\#CNF-SETH]\label[hypothesis]{hyp:sharpcnfseth}
The same statement for computing the number of satisfying assignments.
\end{hypothesis}

\begin{hypothesis}[CNF-ETH]\label[hypothesis]{hyp:cnfeth}
There are $c,\rho>0$ such that satisfiability of CNF formulas with $n$ variables and at most $n^c$
clauses cannot be decided in time $O(2^{\rho n})$.
\end{hypothesis}

\Cref{hyp:cnfseth} implies the form ``no algorithm runs in time $2^{(1-\gamma)n}\poly(M)$'' considered
in~\cite{CDL+16} for instances with $M$ clauses. Indeed, an algorithm of that form runs in time
$O(2^{(1-\gamma/2)n})$ whenever $M\le n^c$. The converse implication is open, because the hard instances of
the latter form might need superpolynomially many clauses. We need the polynomial bound, because the
width reduction of \cref{lem:widthred} branches on clauses. Cygan et al.~\cite{CDL+16} already noted that
SETH could fail while CNF-SAT stays hard; the refutation of ETH realizes the first half of this scenario.
All three hypotheses are monotone in $c$, so we may assume $c\ge1$. \Cref{hyp:cnfseth} implies
\cref{hyp:sharpcnfseth}, because counting decides satisfiability, and it implies \cref{hyp:cnfeth} with
$\rho=1/2$.

\begin{hypothesis}[Max-3-SAT Hypothesis; randomized form of~{\cite[Hypothesis~2.2]{LVWW18}}]\label[hypothesis]{hyp:maxsat}
For every $\gamma>0$, the maximum number of simultaneously satisfiable clauses of a $3$-CNF on $n$
variables cannot be computed in time $O(2^{(1-\gamma)n})$.
\end{hypothesis}

\begin{hypothesis}[Sparse Max-SAT Hypotheses~{\cite[Hypotheses~3 and~4]{AVW20}}]\label[hypothesis]{hyp:sparsemaxsat}
For every $\gamma>0$ there is $c>0$ such that Max-3-SAT on $n$ variables and $cn$ clauses cannot be
solved in time $O(2^{(1-\gamma)n})$. For every $\gamma>0$ there is $c>0$ such that Max-2-SAT on $n$
variables and $cn$ clauses cannot be solved in time $O(2^{(\omega/3-\gamma)n})$, where $\omega$ is the
exponent of matrix multiplication.
\end{hypothesis}

A $3$-CNF on $n$ variables has fewer than $8n^3$ clauses, so \cref{hyp:maxsat} concerns instances of
polynomial size. Bringmann, Cassis, Fischer and K\"unnemann~\cite{BCFK22} base their fine-grained
approximability classification on the Max-3-SAT hypotheses. The last hypothesis measures satisfiability
by formula length, at the rate that the new algorithms make natural.

\begin{hypothesis}[Length form of ETH at rate $C$]\label[hypothesis]{hyp:leneth}
For $C>0$, the hypothesis $\lenETH{C}$ states that no randomized algorithm with error probability at
most $1/3$ decides satisfiability of every CNF formula of length $L$ in time $2^{L/(\log L)^C}$, for all
sufficiently large $L$.
\end{hypothesis}

A CNF of length $L$ becomes an equisatisfiable $3$-CNF with at most $2L$ variables and at most $L$
clauses when we split long clauses with fresh variables. \Cref{fact:claude} decides it in time
$2^{3C_1L/\sqrt{\log L}}$. So $\lenETH{C}$ is false for $C<1/2$ and open for $C\ge1/2$. It states that the
new algorithms are optimal up to polylogarithmic factors in the exponent. Before 2026, the fastest
algorithms for SAT parameterized by length ran in time $2^{cL}$ with $c\approx0.089$~\cite{Hir00,Wah05,CL09,PX23},
and ETH made $2^{\Omega(L)}$ the truth. The form of the hypothesis is not new. Stearns and Hunt~\cite{SH90}
measured SAT by the length of the instance. Chen, Rothblum, Tell and Yogev~\cite{CRTY23} studied the
hypothesis that 3-SAT has no randomized algorithm that runs in time $2^{n/\polylog n}$ in the input
length $n$. The hypothesis $\lenETH{C}$ is the instance of this form with an explicit rate, calibrated so that
the new algorithms refute it exactly for $C<1/2$.