\section{Learning theory after ETH: a ledger}\label{sec:ledger}

Two kinds of statements need a new basis: the hypotheses, and the lower bounds proved from them.
This section takes stock of both. \Cref{tab:hyp} records the hypotheses, \cref{sec:transfer} gives the
rule by which ETH-based bounds transfer, and \cref{tab:learning} applies it to the conditional lower
bounds of learning theory.

\subsection{Hypotheses}\label{sec:hyp-ledger}

\begin{table}[h]
\centering\small
\begin{tabular}{@{}L{5.9cm}L{2.6cm}L{6.1cm}@{}}
\toprule
Hypothesis & Status & Reason\\
\midrule
ETH and SETH ($k$-SAT form)~\cite{IP01}, randomized ETH, \#ETH~\cite{DHM+14}, \#SETH, NSETH~\cite{CGI+16}, Gap-ETH~\cite{Din16,MRa17} & false & each implies ETH~\cite{OAI26,Cla26}\\
Sparse Max-3-SAT and Max-2-SAT~\cite{AVW20} & false & \cref{cor:sparsemaxsat}\\
$\lenETH{C}$ (\cref{hyp:leneth}) & false for $C<\frac12$, open for $C\ge\frac12$ & SAT of length $L$ takes time $2^{O(L/\sqrt{\log L})}$\\
Almost-ETH~\cite{Man26}, Weak ETH~\cite{Aar26} & open & implied by $\lenETH{C}$ for every $C$\\
CNF-SETH, \#CNF-SETH, CNF-ETH & open & hard instances need superlinearly many clauses (\cref{prop:sparsecnf}); width $O(\log n)$ suffices (\cref{lem:widthred})\\
Max-3-SAT (\cref{hyp:maxsat}) & open & superlinear size; Max-SAT does not sparsify\\
OV in dimension $\polylog n$ & open & implied by CNF-SETH~\cite{Wil05}\\
OV in dimension $c\log n$~\cite{GIKW19} & open & no longer known to follow from a hypothesis about SAT (\cref{prop:sparsecnf})\\
$k$-Clique, 3SUM, APSP, Set Cover, Hitting Set~\cite{AVW16}, planted clique, $k\times k$ permutation clique~\cite{LMS18s} & open & not statements about bounded-width SAT with linearly many clauses\\
\bottomrule
\end{tabular}
\caption{Fine-grained hypotheses after the refutation of ETH.}
\label{tab:hyp}
\end{table}

The hard instances of CNF-SETH must have superlinearly many clauses. This follows from the duality
between clause width and clause density of Calabro, Impagliazzo and Paturi~\cite{CIP06} together with the
new algorithms.

\begin{restatable}[Sparse CNF-SAT is subexponential]{proposition}{propsparsecnf}\label[proposition]{prop:sparsecnf}
For all constants $c,\eps'>0$, the number of satisfying assignments of a CNF formula with $n$ variables
and at most $cn$ clauses of arbitrary width can be computed in time $O(2^{\eps'n})$.
\end{restatable}

\begin{proof}[Proof sketch]
Branch with the procedure of \cref{lem:widthred} for a large constant $k$. There are at most
$(n+1)(e(ck+1))^{n/k}=2^{O(n\log(ck)/k)}$ leaves, each a $k$-CNF, and \cref{fact:claude} counts each leaf in
time $2^{o(n)}$ (\cref{app:ledger}).
\end{proof}

Williams' reduction~\cite{Wil05} turns CNF-SAT with $n$ variables and $M$ clauses into Orthogonal Vectors
with $2^{n/2}$ vectors in dimension $M$. Through sparsification, SETH thus implied that OV needs time
$n^{2-o(1)}$ already in dimension $c\log n$. By \cref{prop:sparsecnf}, this route now starts from a false
statement. With polynomially many clauses, the same reduction shows that CNF-SETH implies the hardness of
OV in dimension $\polylog n$.

Two weaker replacements of ETH appeared within a day of the refutation. Weak ETH asks for time
$2^{n^{1-o(1)}}$ for 3-SAT~\cite{Aar26}, and Almost-ETH excludes time $2^{n^{1-\gamma}}$ for every constant
$\gamma>0$~\cite{Man26}. Both are implied by $\lenETH{C}$, and both suffice for bounds with polynomial slack,
such as the hardness of approximating Densest $k$-Subgraph in~\cite{Man26}. Composed with a quasi-linear
PCP, they give only bounds of the form $2^{N^{1-\gamma}}$. The hypothesis $\lenETH{C}$ is the fine-grained
version. It measures the instance by its length for two reasons. Tseitin transformations and quasi-linear
PCPs change the length only by polylogarithmic factors, and the new algorithms run in time
$2^{O(L/\sqrt{\log L})}$ in the length.

\subsection{How lower bounds transfer}\label{sec:transfer}

Consider a lower bound proved from ETH by a reduction that maps a $3$-CNF of length $L$, in time
polynomial in its output, to an equivalent instance of size $N$ with parameter $k$. A CNF of length $L$
becomes a $3$-CNF of length at most $3L$ by splitting clauses, so the reduction applies to every CNF. Assume
that $k\log N\le L(\log L)^\beta$ and $L\le(k\log N)^{O(1)}$. An algorithm that solves the target in time
$N^{k/g}$ then decides SAT of length $L$ in time $2^{O(L(\log L)^\beta/g)}+2^{O(L(\log L)^\beta/k)}$, where the
second term pays for the reduction. Under $\lenETH{C}$, for every $\theta>0$, no algorithm therefore solves the
target in time $N^{k/(\log(k\log N))^{C+\beta+\theta}}$. The bound is meaningful when $k\ge(\log(k\log
N))^{C+\beta+\theta}$; for smaller $k$ its exponent is below $1$. In the same way, a bound $2^{\Omega(n)}$ proved by
a reduction of size $n\le L(\log L)^\beta$ becomes $2^{n/(\log n)^{C+\beta+\theta}}$. The lower bounds of learning
theory then fall into six groups. \Cref{tab:learning} lists examples of each.
\begin{table}[!t]
\centering\small
\begin{tabular}{@{}L{4.7cm}L{2.3cm}c L{6.6cm}@{}}
\toprule
Lower bound & Original hypothesis & Group & Status and surviving hypothesis\\
\midrule
VC and Littlestone dimension, $n^{\log^{1-o(1)}n}$~\cite{MR17} & randomized ETH & 1 & unchanged under Almost-ETH\\
Robust proper halfspaces with margin~\cite{DKM19} & randomized ETH & 1 & unchanged under Almost-ETH\\
Training $k\ge2$ ReLUs, $2^{o(1/\eps)}$~\cite{GKMR21} & Gap-ETH & 2 & $2^{(1/\eps)/\polylog(1/\eps)}$ under $\lenETH{C}$\\
Decision trees with queries~\cite{KST23focs} & ETH & 2 & $2^{\sqrt N/\polylog N}$ under $\lenETH{C}$\\
Sample--time tradeoffs~\cite{BKST25} & randomized ETH & 2 & $2^{n/\polylog n}$ under $\lenETH{C}$\\
Proper decision trees, $n^{\tilde\Omega(\log\log s)}$~\cite{KST23soda} & randomized ETH & 3 & superpolynomial under $\lenETH{C}$ only for small $C$\\
Partial MCSP and MFSP~\cite{Ila20,Ila21} & ETH & 3, 4 & as above; unchanged under permutation hardness~\cite{LMS18s}\\
Proper $k$-juntas, $n^{k-o(1)}$~\cite{KST23soda} & randomized SETH & 4 & unchanged under CNF-SETH~\cite{PW10}\\
ReLU training, $n^{\Omega(d)}$~\cite{FHN22} & ETH & 4 & unchanged under the $k$-Clique hypothesis\\
Training one ReLU, $2^{o(1/\eps^2)}$~\cite{GKMR21} & bounded-degree Densest $k$-Subgraph & 4 & unaffected\\
Adversarially robust halfspaces~\cite{DKM20} & Gap-ETH & 5 & no replacement known\\
Kernel ERM, network gradients, $n^{2-o(1)}$~\cite{BIS17} & SETH & 6 & unchanged under CNF-SETH for $d=\polylog n$\\
Attention with entries $\Theta(\sqrt{\log n})$~\cite{AS23,AS24grad} & SETH & 6 & unchanged under low-dimensional OV\\
VC dimension, $2^{\Omega(|V|)}$~\cite{FGMT25} & ETH, via 3-coloring & -- & basis lost; the source problem is subexponential\\
Inference needs bounded treewidth~\cite{KB09,KBG10} & ETH & -- & $2^{\tw/\polylog\tw}$ under $\lenETH{C}$ (\cref{cor:inflen}); $2^{(1-\gamma)\tw}$ under \#CNF-SETH once $n=\tw^{O(1)}$ (\cref{thm:inflower})\\
Permutation problems, $2^{\Omega(k\log k)}$~\cite{LMS18s,CFG+17} & ETH & -- & basis lost; a hypothesis of its own (\cref{sec:permutation})\\
Proper $k$-term DNF & CNF-SETH & -- & $2^{(1/2-\gamma)n}$ (\cref{prop:dnf})\\
\bottomrule
\end{tabular}
\caption{Conditional lower bounds of learning theory and their status. The groups refer to
\cref{sec:transfer}.}
\label{tab:learning}
\end{table}
\begin{enumerate}[label=(\arabic*)]
\item \emph{Bounds with built-in slack survive under Almost-ETH.} Bounds of the form $n^{\log^{1-o(1)}n}$ or
$2^{n^{1-o(1)}}$ need only Almost-ETH, and so they survive under $\lenETH{C}$. Examples are the hardness of
computing the VC and Littlestone dimensions~\cite{MR17} and of robust proper learning of halfspaces with a
margin~\cite{DKM19}. The hardness of proper learning of decision trees in~\cite{ABF+08} also has a hypothesis
of this form.
\item \emph{Bounds from near-linear reductions lose a polylogarithmic factor in the exponent.} This covers the
exact training of ReLU networks and the training of two or more ReLUs~\cite{GKMR21}, proper learning of
decision trees with queries~\cite{KST23focs}, whose $\tilde O(n^2)$ reduction gives $2^{\sqrt N/\polylog N}$, the
computational--statistical tradeoffs of~\cite{BKST25}, and the ETH-based inapproximability of the VC
dimension~\cite{Man23}. Bounds proved from Gap-ETH through a near-linear PCP join this group through
\cref{cor:gapsat}. The route from ETH through nearly-linear PCPs is the one used in~\cite{DKM19,GKMR21,Man23};
the new point is that its hypothesis survives.
\item \emph{Bounds whose parameter is $O(\log\log N)$ keep almost nothing.} Examples are the bounds
$n^{\tilde\Omega(\log\log s)}$ for proper learning of decision trees of size $s$~\cite{KST23soda} and
$N^{\Omega(\log\log N)}$ for partial MCSP and MFSP~\cite{Ila20,Ila21}. Under $\lenETH{C}$ they keep only a
$(\log\log N)^{-C-O(1)}$ fraction of their exponent, so they remain superpolynomial only for small $C$.
\item \emph{Bounds from other hypotheses survive verbatim.} Consistency and proper learning of $k$-juntas
need time $n^{k-o(1)}$ under CNF-SETH, because $k$-Dominating Set, which needs this time under
CNF-SETH~\cite{PW10}, is a special case of $k$-junta consistency. Label the indicator of each closed
neighborhood $1$ and the all-zero example $0$. A junta on a set $J$ separates each neighborhood from the
zero example only if $J$ meets the neighborhood, so $J$ dominates the graph; conversely, the disjunction of
a dominating set is consistent. ReLU training is W[1]-hard in the dimension $d$ and needs time $n^{\Omega(d)}$
under the hypothesis that $k$-Clique has no $n^{o(k)}$ algorithm~\cite{FHN22}. The inapproximability of the VC
dimension also follows from planted-clique hypotheses~\cite{Man23}. The bounds for partial MCSP survive if
one takes the hardness of $k\times k$ Permutation Clique, $2^{\Omega(k\log k)}$, as a hypothesis of its
own~\cite{LMS18s}.
\item \emph{Bounds from parameterized gap hypotheses have no replacement yet.} Gap-ETH gave $n^{o(k)}$ lower
bounds for parameterized label cover, which underlie the bounds of~\cite{DKM20,KST24focs}. \Cref{cor:gapsat}
gives gap hardness without a parameter, and re-deriving these bounds is open.
\item \emph{Polynomial-time bounds through Orthogonal Vectors keep their statement but change their basis.}
These are $n^{2-o(1)}$ bounds stated under SETH, and the new algorithms give nothing subquadratic for OV.
Bounds whose proofs need sparsification, typically through OV in dimension $\Theta(\log n)$, now rest on the
low-dimensional OV hypothesis alone. They include the thresholds for fast attention and its gradients at
entries of size $\sqrt{\log n}$~\cite{AS23,AS24grad} and its tensor version~\cite{AS24tensor}, the transition for
Gaussian kernel density estimation~\cite{AA22}, the dichotomy for linear algebra on geometric
graphs~\cite{ACSS20}, and the hardness of approximate nearest neighbors and maximum inner
product~\cite{Rub18,ARW17}. Bounds proved for every $d=\omega(\log n)$ by reductions polynomial in $d$, such as
those for kernel methods and neural-network ERM~\cite{BIS17}, self-attention~\cite{KWH23} and hierarchical
clustering~\cite{ACH19}, hold under CNF-SETH for $d=\polylog n$, through the reduction of~\cite{Wil05} with
polynomially many clauses. Bounds stated under \#SETH, such as the tight treewidth bounds for counting
list homomorphisms~\cite{FMR22}, survive under \#CNF-SETH exactly when their reductions start from CNF-SAT
without sparsification. Bounds based on APSP or $k$-Clique, such as the one for the Viterbi
algorithm~\cite{BT17}, are unaffected.
\end{enumerate}

The single-ReLU bound of~\cite{GKMR21} rests on a hypothesis about Densest $k$-Subgraph on bounded-degree
graphs, a sparse problem. Our engine does not refute it. Tracking the size of a vertex set and the number
of edges inside it needs a second formal variable. Its Kronecker substitution needs truncation order
$\Theta(n^2)$, beyond the range of \cref{fact:contract}.

\subsection{The dense side: juntas and DNF}\label{sec:dnf}

Juntas are the canonical non-local class: whether a description selects a variable affects the label
of every example. The lower bound for juntas in group~(4) therefore fits the locality principle. Proper
DNF learning shows the same contrast inside one reduction. Pitt and Valiant~\cite{PV88} reduce graph
$k$-coloring to $k$-term DNF consistency in dimension $n$, with one coordinate for each vertex. Graph
$k$-coloring is now subexponential~\cite[Corollary~1.3]{OAI26}, so the instances of this reduction are
easy. The same reduction applied to \emph{hypergraphs} with edges of unbounded size survives: under
CNF-SETH, consistency for $k$-term DNF in dimension $n$ needs time $2^{(1/2-\gamma)n}$
(\cref{prop:dnf} in \cref{app:ledger}).