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

\paragraph{The refutation of ETH and learning.}
OpenAI~\cite{OAI26} and Anthropic~\cite{Cla26} refuted ETH by counting the solutions of $k$-CNFs in time
$2^{n/(\log n)^{1/2-o(1)}}$, by polynomial interpolation and by signed sums of tensor networks. The companion
paper~\cite{Li26} derived the locality principle for proper learning, error-profile algorithms for exact
empirical risk minimization, agnostic and private learning, the transitions in locality, accuracy and
treewidth, and a ledger of the conditional lower bounds of learning theory; we use its statements as black
boxes. Bhattacharjee~\cite{Bha26} runs the algorithm of~\cite{OAI26} over arbitrary commutative
$\Q$-algebras, which gives weighted counting with several linear statistics at once.

\paragraph{In-context learning.}
Garg, Tsipras, Liang and Valiant~\cite{GTLV22} trained transformers to learn simple function classes in
context. Akyürek et al.~\cite{ASA+23}, von Oswald et al.~\cite{vONR+23} and Bai et al.~\cite{BCW+23} showed
that transformers can implement gradient descent, least squares, ridge regression and algorithm selection in
context, with statistical guarantees. Xie, Raghunathan, Liang and Ma~\cite{XRLM22} explained in-context learning
as implicit Bayesian inference, prior-fitted networks~\cite{MHPGH22} are trained to approximate posterior
predictives, and Panwar, Ahuja and Goyal~\cite{PAG24} compared trained transformers with Bayes predictors on
several task families. Raventós, Paul, Chen and Ganguli~\cite{RPCG23} observed the transition from the Bayes
estimator of the pretraining distribution to ridge regression as task diversity grows. Bhattamishra et
al.~\cite{BPBK24} studied in-context learning of discrete function classes. Pérez, Barceló and
Marinkovic~\cite{PBM21} and Merrill and Sabharwal~\cite{MS24} studied the computational power of transformers
with intermediate generation. These works concern what in-context learners compute and how well they
generalize; the present paper concerns the computational cost of Bayes-optimal in-context prediction.

\paragraph{Bayesian learning curves, halving and version spaces.}
The halving algorithm goes back to Barzdin and Freivald and to Littlestone~\cite{BF72,Lit88}. Haussler, Kearns
and Schapire~\cite{HKS94} bounded the learning curves of the Bayes and Gibbs algorithms by information gain and
VC dimension. The log-loss regret of Bayes mixtures is standard~\cite{CBL06}. Sampling by self-reducibility is
due to Jerrum, Valiant and Vazirani~\cite{JVV86}.

\paragraph{Proper and improper learning.}
Pitt and Valiant~\cite{PV88} showed that proper learning can be NP-hard when improper learning is easy, as for
$k$-term DNF and $k$-CNF; \cref{cor:price} is a fine-grained, exponential-time form of this contrast for Bayes
prediction. The $\ell_1$ regression algorithm is that of Kalai, Klivans, Mansour and Servedio~\cite{KKMS08}.
Daniely, Linial and Shalev-Shwartz~\cite{DLSS13} showed that more data speeds up improper learning of
halfspaces over sparse vectors, which complements the sample price of \cref{thm:regression}.

\paragraph{Local pseudorandom generators.}
Goldreich proposed random local functions as one-way functions~\cite{Gol00}; Applebaum's survey~\cite{App16}
covers their use as pseudorandom generators. O'Donnell and Witmer~\cite{OW14} gave evidence for polynomial
stretch, and Kothari, Mori, O'Donnell and Witmer~\cite{KMOW17} and Feldman, Perkins and
Vempala~\cite{FPV18} proved sum-of-squares and statistical-query lower bounds for refuting and solving random
and planted constraint satisfaction problems. Daniely and Vardi~\cite{DV21} derived hardness of improper PAC
learning from local pseudorandom generators. Learning parity with noise is solved by the algorithm of Blum,
Kalai and Wasserman~\cite{BKW03}. The step from prediction to distinguishing is Yao's~\cite{Yao82}.