\section{Introduction}\label{sec:intro}

The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi~\cite{IP01} states that $3$-SAT on $n$
variables needs time $2^{\Omega(n)}$. For a quarter century it was the standard way to turn NP-hardness
into quantitative lower bounds. Its relatives did the same for exact constants (SETH), for approximation
(Gap-ETH) and for counting (\#ETH). Learning theory used all of them. ETH and Gap-ETH give lower
bounds for proper learning of decision trees~\cite{KST23soda,KST23focs,KST24focs} and for computing the
VC and Littlestone dimensions~\cite{MR17,Man23}. They also give lower bounds for training neural
networks~\cite{GKMR21,FHN22}, for robust proper learning of halfspaces~\cite{DKM19,DKM20}, and for
computational--statistical tradeoffs~\cite{BKST25}. SETH gives quadratic lower bounds for kernel methods,
attention and nearest neighbors~\cite{BIS17,AS23,ACSS20,Rub18}. In inference, ETH was the basis of the
conclusion that bounded treewidth is necessary for efficient inference~\cite{KB09,KBG10}.

In October 2026, two independent works refuted ETH~\cite{OAI26,Cla26}. Both count the satisfying
assignments of a $k$-CNF on $n$ variables in deterministic time $2^{n/(\log n)^{1/2-o(1)}}$, with
polynomial dependence on the number of clauses. One works by polynomial interpolation, the other by
signed sums of tensor networks contracted in different orders, and both need sparse instances: linearly
many constraints of bounded width. SETH, Gap-ETH, \#ETH and NSETH each imply ETH, so all of them are
false as well. Two forms survive. CNF-SETH states that CNF-SAT with polynomially many clauses of
unbounded width needs time $2^{(1-\gamma)n}$, and the Max-3-SAT Hypothesis states the same for the maximum
number of satisfiable clauses of a dense $3$-CNF (\cref{sec:hyp}).

This paper determines what the refutation changes in computational learning theory. Which learning
problems become subexponential? Which lower bounds survive, and on which hypothesis? We use the new
algorithms only through the three statements of \cref{sec:imported}.

\subsection{The locality principle}\label{sec:intro-locality}

A learning problem is a constraint satisfaction problem. Its variables are the bits of the hypothesis
description, and its constraints are the labeled examples. For most classical classes, such as DNF,
decision trees and halfspaces on dense data, every example constrains every description bit. The
resulting formulas have clauses of width $\Theta(N)$, and the new algorithms do not reach this regime. The
dividing line is the following notion.

\begin{definition}[Informal; see \cref{def:local}]
A class of hypotheses with $N$-bit descriptions $w\in\{0,1\}^N$ is \emph{$\kappa$-local} if for each example
$x$ there is a set $R(x)\subseteq[N]$ of at most $\kappa$ positions such that the label $h_w(x)$ depends only on
the bits of $w$ in $R(x)$.
\end{definition}

Sparse data make quantized models local. A binarized perceptron $x\mapsto\ind[\langle w,x\rangle\ge0]$ with
$w\in\{\pm1\}^n$ is $k$-local on $k$-sparse inputs, because only the weights on the support of $x$ matter.
With $b$-bit weights, and for quantized embedding models and factorization machines on bags of $k$
tokens, the locality is $\kappa=bk$. Two-layer binarized networks with $r$ hidden units are
$(rk+r)$-local. A graphical model of bounded degree and arity is local in the same sense: each factor
reads a bounded number of variables. Our main finding is a principle.

\begin{center}
\begin{minipage}{0.86\linewidth}
\emph{The new algorithms speed up learning when each labeled example constrains few bits of the
hypothesis description. Under CNF-SETH the speed-up ends when examples constrain $\Theta(\log N)$ bits.}
\end{minipage}
\end{center}

Three transitions make the principle precise. \Cref{fig:transitions} summarizes them.

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,
  reg/.style={font=\footnotesize,align=center,text width=#1},
  tk/.style={font=\footnotesize,anchor=north},
  ttl/.style={font=\small\bfseries,anchor=south west,inner sep=0pt}]
% ---------- row 1: locality ----------
\node[ttl] at (0,7.75) {Locality $\kappa$ \ (consistency and proper learning at accuracy $N^{-O(1)}$; hardness for $\BP$)};
\fill[easy!30] (0,6.7) rectangle (4.2,7.5);
\fill[open!25] (4.2,6.7) rectangle (9.3,7.5);
\fill[hard!30] (9.3,6.7) rectangle (15.2,7.5);
\draw[thin,black!50] (0,6.7) rectangle (15.2,7.5);
\node[reg=4.0cm] at (2.1,7.1) {$2^{o(N)}$, unconditional};
\node[reg=4.9cm] at (6.75,7.1) {equivalent to $k$-SAT\\ with $k=(\log N)^{\Theta(1)}$};
\node[reg=5.7cm] at (12.25,7.1) {$2^{(1-\gamma)N}$ under CNF-SETH};
\node[tk,anchor=north west] at (0,6.65) {$1$};
\node[tk] at (4.2,6.65) {$(\log N)^{1/4-o(1)}$};
\node[tk] at (9.3,6.65) {$K\log N$};
\draw[easy,very thick,decorate,decoration={brace,amplitude=4pt,mirror}] (0,6.05) -- (6.6,6.05)
  node[midway,below=4pt,font=\footnotesize] {at constant accuracy: $2^{o(N)}$ up to $\kappa=o(\sqrt{\log N})$};
\node[tk] at (6.6,6.65) {$\sqrt{\log N}$};
% ---------- row 2: accuracy ----------
\node[ttl] at (0,4.65) {Inverse accuracy $1/\eps$ \ (proper agnostic learning; hardness for $\LD_3$)};
\fill[easy!30] (0,3.6) rectangle (5.4,4.4);
\fill[open!25] (5.4,3.6) rectangle (10.2,4.4);
\fill[hard!30] (10.2,3.6) rectangle (15.2,4.4);
\draw[thin,black!50] (0,3.6) rectangle (15.2,4.4);
\node[reg=5.2cm] at (2.7,4.0) {$2^{o(N)}$; at constant $\eps$ it is\\ $2^{N/\polylog N}$ under $\mathrm{ETH}^{\mathrm{len}}$};
\node[reg=4.6cm] at (7.8,4.0) {open};
\node[reg=4.8cm] at (12.7,4.0) {$2^{(1-o(1))N}$ under Max-3-SAT};
\node[tk,anchor=north west] at (0,3.55) {constant};
\node[tk] at (5.4,3.55) {$(\log N)^{1/4}$};
\node[tk] at (10.2,3.55) {$8N^{3}$};
% ---------- row 3: treewidth ----------
\node[ttl] at (0,2.15) {Model size $n$ versus treewidth \ (exact inference, bounded degree and arity)};
\fill[easy!30] (0,1.1) rectangle (5.4,1.9);
\fill[open!25] (5.4,1.1) rectangle (10.2,1.9);
\fill[hard!30] (10.2,1.1) rectangle (15.2,1.9);
\draw[thin,black!50] (0,1.1) rectangle (15.2,1.9);
\node[reg=5.2cm] at (2.7,1.5) {$2^{o(\tw)}$, beats elimination; it is\\ $2^{\tw/\polylog\tw}$ under $\mathrm{ETH}^{\mathrm{len}}$};
\node[reg=4.6cm] at (7.8,1.5) {\#SAT by formula length};
\node[reg=4.8cm] at (12.7,1.5) {$2^{(1-\gamma)\tw}$ under \#CNF-SETH};
\node[tk,anchor=north west] at (0,1.05) {$n=\tw$};
\node[tk] at (5.4,1.05) {$\tw\sqrt{\log\tw}$};
\node[tk] at (10.2,1.05) {$\tw^{O(1)}$};
% ---------- legend ----------
\fill[easy!30] (0.0,-0.2) rectangle (0.35,0.1); \node[anchor=west,font=\footnotesize] at (0.4,-0.05) {subexponential, unconditional};
\fill[open!25] (5.2,-0.2) rectangle (5.55,0.1); \node[anchor=west,font=\footnotesize] at (5.6,-0.05) {open};
\fill[hard!30] (7.2,-0.2) rectangle (7.55,0.1); \node[anchor=west,font=\footnotesize] at (7.6,-0.05) {exponent $1-o(1)$ under a surviving hypothesis};
\end{tikzpicture}
\caption{The three transitions. Each row is a parameter that grows to the right; the regimes are not
drawn to scale. Green regions are upper bounds that use only the new algorithms~\cite{OAI26,Cla26}; the
lower bounds in green regions assume $\lenETH{C}$. Row~1:
\cref{thm:realizable,thm:moderate,thm:equivalence,thm:barrier}. Row~2:
\cref{thm:agnostic,thm:constacc,thm:accbarrier}. Row~3:
\cref{thm:inference,cor:separation,cor:inflen,thm:inflower,cor:twtransition}.}
\label{fig:transitions}
\end{figure}

\paragraph{Transition 1: locality.}
For local classes, the version space of a sample is the solution set of a $\kappa$-CNF, so every
computation on it reduces to counting $\kappa$-CNFs. Conversely, a padding gadget embeds $k$-SAT into
binarized perceptrons on $2k$-sparse data.

\begin{headline}[Locality; \cref{thm:realizable,thm:equivalence,thm:barrier,thm:moderate}]\label{thm:A}
Let $\cH$ be a $\kappa$-local class with $N$-bit descriptions.
\begin{enumerate}[label=(\arabic*)]
\item Exact counting and uniform sampling of version spaces, the halving algorithm, and proper PAC
learning at every accuracy run in time $\poly(m)\cdot2^{O(\kappa^2N\log\log N/\sqrt{\log N})}$. At constant
accuracy, proper PAC learning runs in time $2^{O(\kappa N/\sqrt{\log N}+\kappa^2)}$.
\item At inverse-polynomial accuracy, and up to a factor $2$ in the locality, proper learning of
$\kappa$-local classes is equivalent to $\kappa$-SAT.
\item Under CNF-SETH, for every $\gamma>0$ there is $K$ such that consistency and proper PAC learning to
inverse-polynomial accuracy of binarized perceptrons on $(K\log N)$-sparse data need time
$2^{(1-\gamma)N}$.
\end{enumerate}
\end{headline}

For constant $\kappa$, the counting part of (1) is Corollary~C.2 of~\cite{OAI26} in learning terms. New are
the uniformity in $\kappa$, the equivalence (2) and the hardness (3). Consistency and learning to
inverse-polynomial accuracy are thus subexponential up to locality $(\log N)^{1/4-o(1)}$, and as hard as
CNF-SAT at locality $\Theta(\log N)$. Between the two lies the open window of $k$-SAT for
$k=(\log N)^{\Theta(1)}$. At constant accuracy the subexponential range extends to $(\log N)^{1/2-o(1)}$.

\paragraph{Transition 2: accuracy.}
For agnostic learning, the cost depends on the size of the sample, not on $N$. Exact ERM on $m$ examples
reads only $\kappa m$ description bits, and it is a sparse weighted constraint problem. We compute its
entire error profile, the number of hypotheses with exactly $j$ errors for every $j$, by tensor
contraction over the truncated polynomial ring $(\Z/2^P\Z)[V]/(V^\ell)$. The lower bounds use a length form
of ETH. The hypothesis $\lenETH{C}$ states that SAT on CNFs of length $L$ needs time $2^{L/(\log L)^C}$. It is
the instance with an explicit rate of the polylog-slack hypotheses of~\cite{CRTY23}. The new algorithms
refute it for $C<1/2$, and for $C\ge1/2$ it states that they are optimal up to polylogarithmic factors in the
exponent.

\begin{headline}[Accuracy; \cref{thm:erm,cor:ermlen,thm:agnostic,thm:expmech,thm:constacc,cor:satlen,thm:accbarrier}]\label{thm:B}
Let $\cH$ be a $\kappa$-local class with $N$-bit descriptions and VC dimension $d$.
\begin{enumerate}[label=(\arabic*)]
\item Exact ERM, the error profile and the exponential mechanism on a sample of size $m\ge\max\{\kappa,2\}$
take time $\poly(N)\cdot2^{O(\kappa m/\sqrt{\log m})}$. For literal disjunctions on $3$-sparse data,
consistency on $m$ examples needs time $2^{m/(\log m)^{C+o(1)}}$ under $\lenETH{C}$.
\item Proper agnostic learning takes time $\poly(N)\cdot2^{O(\kappa d/(\eps^2\sqrt{\log(2d/\eps)})+\kappa^2)}$ for
constant confidence. At a small constant accuracy $\eps_0$, proper learning of literal disjunctions on
$3$-sparse data, realizable or agnostic, needs time $2^{N/(\log N)^{C+O(1)}}$ under $\lenETH{C}$. So at
constant accuracy, proper learning of constant-local classes is SAT parameterized by formula length, up
to polylogarithmic factors in the exponent.
\item Under the Max-3-SAT Hypothesis, proper agnostic learning of literal disjunctions on $3$-sparse
data to accuracy $1/(8N^3)$ needs time $2^{(1-o(1))N}$.
\end{enumerate}
\end{headline}

With the quasi-linear PCPs of Dinur and of Ben-Sasson and Sudan~\cite{Din07,BS08}, $\lenETH{C}$ replaces
Gap-ETH for gap reductions of quasi-linear size, at a polylogarithmic loss in the exponent
(\cref{cor:gapsat}). At inverse-polynomial accuracy, more data makes exact ERM harder: it is
subexponential on samples of size $o(N\sqrt{\log N})$ and needs time $2^{(1-o(1))N}$ on samples of size
$\Theta(N^3)$.

\paragraph{Transition 3: treewidth.}
Exact inference in graphical models is \#SAT parameterized by the length of the model, and the textbook
algorithms take time exponential in the treewidth.

\begin{headline}[Treewidth; \cref{thm:inference,cor:separation,cor:inflen,thm:inflower,cor:twtransition}]\label{thm:C}
Consider Boolean graphical models of bounded degree and arity with small nonnegative integer weights.
\begin{enumerate}[label=(\arabic*)]
\item On $n$ variables, the partition function, all marginals, and a minimum-energy assignment can be
computed exactly in time $2^{O(n/\sqrt{\log n})}$. On bounded-degree expanders, every elimination order and
every structured DNNF needs time or size $2^{\Omega(n)}$. Under $\lenETH{C}$, deciding whether the partition
function is positive needs time $2^{\tw/(\log\tw)^{C+o(1)}}\poly(n)$.
\item Under \#CNF-SETH, for every $\gamma>0$, no algorithm computes partition functions in time
$2^{(1-\gamma)\tw}\poly(n)$, already on models with $n\le\tw^{O(1)}$ variables.
\end{enumerate}
\end{headline}

The treewidth-based algorithms take time $2^{\Theta(\tw)}$. So they are not optimal when the model has
$n=O(\tw)$ variables, but they are optimal again when $n$ may be polynomially larger than $\tw$.
The preprint~\cite{Cla26} already notes that its algorithm beats every fixed tree of cuts on expanders;
the inference statements and both lower bounds are new. The ETH-based bound of~\cite{KB09,KBG10} has lost
its proof. Part (1) puts a bound of the form $2^{\tw/\polylog\tw}$ on the surviving hypothesis $\lenETH{C}$,
and the qualitative statement that inference is not polynomial in the treewidth rests on NP not having
polynomial-size circuits~\cite{CSH08,CC16}.

\paragraph{By-products for fine-grained complexity.}
Three results do not concern learning.
\begin{itemize}
\item Exact Max-SAT with $cn$ clauses takes time $2^{O((1+c)n/\sqrt{\log n})}$, so the Sparse Max-SAT
Hypotheses of Alman and Vassilevska Williams~\cite{AVW20} are false (\cref{cor:sparsemaxsat}). This also
follows from~\cite[Theorem~1.1]{OAI26} with a threshold circuit; the error profile gives in addition the
whole distribution of the number of violated clauses.
\item Under CNF-SETH, a \#$k$-SAT algorithm with exponent $k^\mu n/(\log n)^\nu$ needs $\mu\ge\nu$
(\cref{cor:kdep}). A better rate must come with a worse dependence on $k$.
\item CNF-SAT with linearly many clauses of arbitrary width is subexponential (\cref{prop:sparsecnf}). So
the hard instances of CNF-SETH have superlinearly many clauses, and the hardness of low-dimensional
Orthogonal Vectors no longer follows from a hypothesis about SAT.
\end{itemize}

\paragraph{What survives.}
\Cref{sec:ledger} takes stock of the conditional lower bounds of learning theory. Bounds stated with
polynomial slack, such as the hardness of computing the VC dimension~\cite{MR17}, survive under
Almost-ETH~\cite{Man26}, and so under $\lenETH{C}$. Bounds from near-linear reductions survive under
$\lenETH{C}$ with a polylogarithmic loss in the exponent. Bounds whose exponent is only $\Theta(\log\log
N)$, such as those for proper learning of decision trees~\cite{KST23soda} and for partial MCSP~\cite{Ila20},
keep almost nothing. Bounds that rest on CNF-SETH or on $k$-Clique survive verbatim. Among them is the
$n^{k-o(1)}$ bound for juntas, the canonical non-local class. The quadratic SETH-based bounds for attention
and kernel density estimation are not contradicted, but they now rest on the low-dimensional OV
hypothesis alone. The next obstacle is permutations. On difference vectors $e_i-e_j$, ERM for real-valued
halfspaces is weighted Feedback Arc Set (\cref{prop:fas}), and the new algorithms do not reach it.

\paragraph{What is new.}
The two preprints~\cite{OAI26,Cla26} contain no statement about learning. \Cref{lem:vscnf} is the encoding
of~\cite[Corollary~C.2]{OAI26}, and the upper bound for counting at constant locality is that corollary.
Everything else is new: the locality principle with bounds uniform in $\kappa$, the equivalence with
$\kappa$-SAT and the hardness at logarithmic locality, the error-profile algorithms for ERM, agnostic and
private learning, the lower bounds at constant and inverse-polynomial accuracy, the results on inference,
the by-products above, and the ledger.

\subsection{Techniques}\label{sec:techniques}

\paragraph{Version spaces as CNFs.}
Each example excludes at most $2^\kappa$ patterns of its $\kappa$ relevant bits. So the version space is the
solution set of a $\kappa$-CNF with at most $m2^\kappa$ clauses (\cref{lem:vscnf}). The algorithm of~\cite{Cla26}
counts its solutions in time $2^{O(\kappa^2N\log\log N/\sqrt{\log N})}$ independently of $m$, and sampling,
halving and learning follow by self-reducibility. For the converse, a padding gadget turns a clause into a
sparse example. Its inner product with a sign vector is $2t-2$, where $t$ is the number of true literals
(\cref{lem:gadget}).

\paragraph{The error profile as one contraction.}
Agnostic learning needs the number of hypotheses with exactly $j$ errors for every $j$. An example
contributes the factor $1$ when it is fit and $V$ when it is not, and the contraction theorem
of~\cite{OAI26} over $(\Z/2^P\Z)[V]/(V^\ell)$ computes the product sum. Three choices make it exact. We
restrict to the $\kappa m$ description bits that the sample reads. We turn the factor graph into a
bipartite Boolean tensor network of degree $\max\{\kappa,3\}$ (\cref{lem:fg2tn}). And we choose the
precision $P$ and the truncation order $\ell$ so that no coefficient is lost. The cost depends on the total
size $\kappa m$ of the sample instead of $\kappa^2N$, which gives sample-sensitive learning, the exponential
mechanism, and exact sparse Max-CSP.

\paragraph{Lower bounds that control variables, length and accuracy.}
For consistency, a quantitative form of Schuler's width reduction~\cite{Sch05,CIP06} shows that, under
CNF-SETH, $k$-SAT with $k=K\log n$ needs time $2^{(1-\gamma)n}$, with solution counts preserved
(\cref{lem:widthred}). For constant accuracy, a quasi-linear PCP turns a CNF of length $L$ into an $\LD_3$
sample in dimension $L\polylog L$, with perfect completeness and a constant gap (\cref{lem:pcp2ld}). For
inference, OR-chains with copied variables turn any CNF into a degree-$3$ factor graph whose pathwidth is at
most the number of variables plus $2$ (\cref{lem:chain}).

\subsection{Organization}\label{sec:organization}

\Cref{sec:prelim} fixes the model, imports the new algorithms, builds the engine of all our algorithms,
and states the surviving hypotheses. \Cref{sec:locality,sec:accuracy,sec:treewidth} prove the three
transitions. \Cref{sec:ledger} takes stock of the conditional lower bounds of learning theory.
\Cref{sec:related} discusses related work, and \cref{sec:outlook} isolates the permutation obstacle and
lists open problems. The main text gives a proof sketch for each result. \Cref{app:roadmap} explains the
appendix, which contains all full proofs in a structured form.

\paragraph{AI disclosure.}
This paper was written with Claude Opus~5.5 (Anthropic), working as an agent in Claude Code. The author
posed the question and directed the presentation. Claude chose the results, proved them, wrote the text and
drew the figures. Separate Claude agents searched the literature, audited the proofs and reviewed the paper
as referees, and the paper was revised to address their findings. The gadgets and reductions were tested by
brute force on small random instances, and the asymptotic estimates were checked symbolically and in exact
arithmetic. The author is responsible for the content.