\section{Related work}\label{sec:related}

\paragraph{The refutation.}
The two refutations~\cite{OAI26,Cla26} appeared within days of each other. Within a day, Aaronson~\cite{Aar26}
and Manurangsi~\cite{Man26} proposed the replacements Weak ETH and Almost-ETH, which have polynomial slack.
Chen~\cite{Che26} applied the contraction theorem of~\cite{OAI26} to the smallest grammar problem.

\paragraph{Fine-grained hypotheses.}
ETH and SETH are due to Impagliazzo and Paturi~\cite{IP01}, and the sparsification lemma to Impagliazzo,
Paturi and Zane~\cite{IPZ01}. The duality between clause width and clause density is due to Calabro,
Impagliazzo and Paturi~\cite{CIP06}. The CNF form of SETH and the problems equivalent to it are studied
in~\cite{CDL+16,PW10}, the counting versions in~\cite{DHM+14}, NSETH in~\cite{CGI+16}, and Gap-ETH
in~\cite{Din16,MRa17,CCK+20}. The Max-SAT hypotheses are from~\cite{LVWW18,AVW20}, and the classification
of~\cite{BCFK22} builds on them. Hypotheses with polylogarithmic slack in the input length appear
in~\cite{CRTY23}, and the measurement of SAT by instance length goes back to~\cite{SH90}. Before 2026, the
best algorithms for SAT by length~\cite{Hir00,Wah05,CL09,PX23}, by number of clauses~\cite{CXZ21}, and for
\#SAT~\cite{IMP12,CW21} saved constant or $1/O(k)$ factors in the exponent. The Super-Strong
ETH~\cite{VW21} conjectured that the saving $1/O(k)$ for $k$-SAT was optimal. Quasi-linear PCPs are due to
Ben-Sasson and Sudan and to Dinur~\cite{BS08,Din07}; Bafna, Minzer, Vyas and Yun obtain small
soundness~\cite{BMVY25}.

\paragraph{Hardness of learning.}
NP-hardness of proper learning goes back to Pitt and Valiant~\cite{PV88} and Blum and
Rivest~\cite{BR92}; see also~\cite{ABF+08}. Recent conditional bounds concern decision
trees~\cite{KST23soda,KST23focs,KST24focs}, MCSP and learning programs~\cite{Ila20,Ila21,Hir22}, and neural
networks~\cite{GKMR21,FHN22}. Others concern the VC dimension~\cite{MR17,Man23,FGMT25}, robust learning of
halfspaces~\cite{DKM19,DKM20}, parameterized learning~\cite{AKL07,BGS23}, and computational--statistical
tradeoffs~\cite{BKST25}. Decision trees can be learned properly with queries in time
$n^{O(\log\log n)}$~\cite{BLQT21}, and training neural networks is $\exists\mathbb R$-complete~\cite{AKM21,BHJ+23}.
ETH-based bounds also exist for unsupervised learning, for example for nonnegative matrix
factorization~\cite{AGKM12} and for $k$-means and $k$-median clustering in low
dimension~\cite{CdMRR18,CKSS26}; the transfer rule of \cref{sec:transfer} applies to them. Daniely, Linial
and Shalev-Shwartz~\cite{DLSS13} studied halfspaces on sparse data and showed that more data can speed up
improper learning; we study the complementary exponential-time regime of proper learning. SETH-based
quadratic bounds in machine learning
include~\cite{BIS17,KWH23,AS23,AS24grad,AS24tensor,AY25,ACSS20,AA22,Rub18,ARW17,ACH19}. \Cref{sec:ledger}
classifies these results.

\paragraph{Counting, inference and permutations.}
The halving algorithm goes back to Barzdin and Freivald and to Littlestone~\cite{BF72,Lit88}, and
query-by-committee to Seung, Opper and Sompolinsky and to Freund et al.~\cite{SOS92,FSST97}. Sampling by
self-reducibility is due to Jerrum, Valiant and Vazirani~\cite{JVV86}. Approximate counting gives efficient
halving for total orders~\cite{GRS93} and efficient query-by-committee for convex version
spaces~\cite{GNT05}. Counting assignments by their weight goes back to Williams' algorithm for
Max-2-CSP~\cite{Wil05}. The exponential mechanism is due to McSherry and Talwar~\cite{MT07}, and its use as a
generic private learner to Kasiviswanathan et al.~\cite{KLN+11}. Treewidth lower bounds for inference are
in~\cite{CSH08,KB09,KBG10}, building on Marx~\cite{Mar10}. CNF-SAT-based treewidth lower bounds for graph
problems are in~\cite{LMS18tw}, and tight treewidth bounds for counting list homomorphisms are stated under
\#SETH in~\cite{FMR22}. Knowledge compilation needs size $2^{\Omega(\tw)}$ for structured DNNF~\cite{ACMS20}
and $2^{\Omega(n)}$ for every DNNF on suitable expanders~\cite{BCMS14,BCMS16}. Tree-decomposition contraction
is the standard way to evaluate tensor networks~\cite{MS08,KCMR19,DDV19}; the contraction-tree lower bounds
of~\cite{AKK22} are discussed in~\cite{Cla26}. Learning to order is Feedback Arc Set~\cite{CSS99}, which has a
$2^n$ dynamic program~\cite{BFK+12}, and permutation problems have $2^{\Omega(k\log k)}$ lower bounds from
ETH~\cite{LMS18s,CFG+17}.