\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}\\
Gap Densest $k$-Subgraph on bounded-degree graphs~\cite{GKMR21} & false & \cref{prop:dks}\\
3SUM, APSP, Exact Triangle, Zero-, Min- and Max-Weight $k$-Clique & false & truly subquadratic 3SUM and truly subcubic APSP~\cite{AVW26}\\
$\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})\\
Unweighted $k$-Clique, 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 unweighted $k$-Clique hypothesis\\
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\\
Training one ReLU, $2^{o(1/\eps^2)}$~\cite{GKMR21} & bounded-degree Densest $k$-Subgraph & -- & basis lost; the source problem is subexponential (\cref{prop:dks}); $2^{(1/\eps)^{1/9-o(1)}}$ under Almost-ETH (\cref{prop:relu})\\
Viterbi algorithm, $Tn^{2-o(1)}$~\cite{BT17} & APSP, Max-Weight $k$-Clique & -- & basis lost; both hypotheses are false~\cite{AVW26}\\
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 unweighted $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 unweighted $k$-Clique are unaffected.
\end{enumerate}

Two more bounds have lost their basis. The bound for the Viterbi algorithm~\cite{BT17} rests on APSP and
Max-Weight $k$-Clique. Alman and Vassilevska Williams~\cite{AVW26} refute both, along with 3SUM, in the same month
as the refutation of ETH and by a different method, an algorithm for thin matrix products. The single-ReLU bound
of~\cite{GKMR21} rests on a hypothesis about Densest $k$-Subgraph on bounded-degree graphs, a sparse problem, and
\cref{sec:relu} shows that this hypothesis is false.

\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}).

\subsection{The single-ReLU bound}\label{sec:relu}

Goel, Klivans, Manurangsi and Reichman~\cite{GKMR21} train one ReLU with weights in the unit ball to additive
error $\eps$ in time $2^{O(1/\eps^2)}\poly(n,m)$. They prove that time $2^{o(1/\eps^2)}\poly(n,m)$ is impossible under
their Hypothesis~1: for every constant $C\ge1$ there are $\delta>0$ and $d$ such that no algorithm in time
$O(2^{\delta N})$ distinguishes, on graphs with $N$ vertices and maximum degree $d$, whether the densest
$k$-vertex subgraph has at least $\xi$ edges or fewer than $\xi/C$ edges.

This hypothesis is false. Tracking the size of a vertex set and the number of edges inside it takes two
counters. One of them fits into the truncated ring of \cref{fact:contract}. A Kronecker substitution of the
other would need truncation order $\Theta(N^2)$, beyond the range of that theorem. Instead, we evaluate the second
counter at the integer points $0,\dots,D$ and recover its coefficients by interpolation. For $t\ge1$, dividing by
$t!$ costs fewer than $t$ bits of $2$-adic precision, and the precision allowed by \cref{fact:contract} is linear.

\begin{restatable}[Two counters]{lemma}{lemcounters}\label[lemma]{lem:counters}
Let $\Phi$ be a factor graph on $n$ Boolean variables, of arity at most $a$, whose table entries are $0$ or
monomials $V^{e}U^{r}$ with integers $e,r\ge0$, computable in polynomial time. For an assignment $x$ that
avoids the entries $0$, let $A(x)$ and $B(x)$ be the sums of the exponents $e$ and $r$ over the factors. Suppose
that $A(x)<\ell$ and $B(x)\le D$ for all such $x$, and let $s$ be an integer with
$s\ge\max\{4\|\Phi\|,n+D+1,\ell,2\}$ and $a\le s^{9/10}$. Then the number $c_{i,j}$ of such $x$ with $A(x)=i$ and
$B(x)=j$ can be computed deterministically, for all $i$ and $j$, in time
$\poly(s+|\Phi|)\cdot2^{O(s/\sqrt{\log s})}$.
\end{restatable}

\begin{proof}[Proof sketch]
For each $u\in\{0,\dots,D\}$, replace $U$ by $u$ and compute the partition function over $\Ring_{P,\ell}$ with
$P=n+D+1$ by \cref{thm:sumproduct}. The coefficient of $V^i$ is $g_i(u)$ modulo $2^P$, where
$g_i(u)=\sum_jc_{i,j}u^j$. In the basis of falling factorials, $g_i=\sum_tb_t\,u(u-1)\cdots(u-t+1)$ with integers
$b_t$, and the $t$-th forward difference of $g_i$ at $0$ is $t!\,b_t$. By Legendre's formula, $2^{t}$ does not divide
$t!$ for $t\ge1$, so $b_t$ is determined modulo $2^{n+1}$. The $c_{i,j}$ are integer combinations of the $b_t$, and
$0\le c_{i,j}\le2^n$ (\cref{app:ledger}).
\end{proof}

\begin{restatable}[Densest $k$-Subgraph]{proposition}{propdks}\label[proposition]{prop:dks}
Given a graph with $N\ge1$ vertices and $M$ edges, the number of $k$-vertex subsets that induce exactly $j$
edges can be computed, for all $k$ and $j$, deterministically in time
$\poly(N+M)\cdot2^{O(s/\sqrt{\log s})}$ with $s=4(N+2M)$, and a densest $k$-vertex subset can be found in the same
time. On graphs of maximum degree $d=O(1)$ the time is $2^{O(N/\sqrt{\log N})}$, and it is $2^{o(N)}$ for
$d=o(\sqrt{\log N})$. Hence Hypothesis~1 of~\cite{GKMR21} is false.
\end{restatable}

\begin{proof}[Proof sketch]
Each vertex is a variable with the table $(1,U)$, and each edge a factor with the entry $V$ on $(1,1)$ and $1$
elsewhere. Then $A(x)$ is the number of edges inside the chosen set and $B(x)$ is its size, and
\cref{lem:counters} applies with $\ell=M+1$ and $D=N$ (\cref{app:ledger}).
\end{proof}

The same lemma gives the joint error profile of a sample split into two parts, in the time of \cref{lem:profile}
up to a constant in $s$. So it gives exact empirical risk minimization for local classes under a bound on the
errors on one part, as in Neyman--Pearson classification or under a constraint for a protected group.
Concurrently, Bhattacharjee~\cite{Bha26} carries several counters through the interpolation algorithm
of~\cite{OAI26} over $\mathbb Q$, at the rate $(\log\log n)^2/\sqrt{\log n}$, which also allows polynomially large
weights. That route gives the joint profile of size and cut~\cite[Corollary~6.4]{Bha26}, and, with the edge factor
above, the counts of \cref{prop:dks} at that rate; \cite{Bha26} does not consider Densest $k$-Subgraph or ReLUs.

So the bound for one ReLU has lost its proof, and with it the separation between proper and improper agnostic
learning of one ReLU in~\cite{GKMR21}. Two statements remain: the reduction of~\cite{GKMR21} from Densest
$k$-Subgraph with its rate made explicit, and a weaker bound from their reduction from Set Cover, which has
polynomial size and inverse-polynomial additive gap.

\begin{restatable}[One ReLU after the refutation]{proposition}{proprelu}\label[proposition]{prop:relu}
Let $C_*$ be the constant gap used in the proof of~\cite[Theorem~3]{GKMR21}. Consider algorithms that train one
ReLU with weights in the unit ball to additive error $\eps$, for all given $\eps>0$.
\begin{enumerate}[label=(\alph*)]
\item If, for some $a>0$ and some constants $d$ and $\lambda>0$, no algorithm distinguishes the two cases of the gap
problem above with $C=C_*$ and $k\ge\lambda N$ in time $2^{N/(\log N)^a}$, then for every $\theta>0$ no such training
algorithm runs in time $2^{(1/\eps^2)/(\log(1/\eps))^{a+\theta}}\poly(n,m)$.
\item Under Almost-ETH, no such training algorithm runs in time $2^{(1/\eps)^{\alpha}}\poly(n,m)$, for any
$\alpha<1/9$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
For~(a), the reduction of~\cite{GKMR21} maps a graph with $N$ vertices and degree $d$, with $k\ge\lambda N$, to an
instance of size $\poly(N)$ with $\eps=\Theta_{d,\lambda}(1/\sqrt N)$. For~(b), a 3-CNF on $n_0$ variables is a Set
Cover instance of polynomial size, and the reduction of~\cite{GKMR21} from Set Cover, normalized to the unit ball, has
an additive gap of $\Omega(n_0^{-9})$ (\cref{app:ledger}).
\end{proof}

By \cref{prop:dks}, the hypothesis of part~(a) fails for $a<1/2$. It is open for $a\ge1/2$, and it stands on its own:
the hardness of approximating Densest $k$-Subgraph from hypotheses about SAT~\cite{Man26} excludes polynomial time,
not time $2^{N/\polylog N}$. The restriction to $k\ge\lambda N$ comes from the reduction, whose gap shrinks with $k$;
\cite{GKMR21} treat $k=o(N)$ by enumerating subsets, which takes time $2^{o(N)}$ but not $2^{N/\polylog N}$. Whether
one ReLU can be trained in time $2^{o(1/\eps^2)}\poly(n,m)$ is now open (\cref{prob:relu}).