\section{Preliminaries}\label{sec:prelim}

This section fixes the model of in-context learning, imports the results of~\cite{Li26} that we use, and
states the hypotheses that survive the refutation of ETH.

\subsection{Local classes}\label{sec:local}

We write $\log$ for $\log_2$, $[n]$ for $\{1,\dots,n\}$, and $w|_R$ for the restriction of $w\in\{0,1\}^N$ to
$R\subseteq[N]$. A \emph{clause} is a nonempty set of literals, its \emph{width} is its size, a \emph{CNF} is
a finite set of clauses, and a \emph{$k$-CNF} has clauses of width at most $k$. The \emph{length} of a CNF is
its number of literal occurrences, and $\#F$ is the number of satisfying assignments of $F$ on its declared
variables. Time is measured in the word-RAM model.

\begin{definition}[Local class~{\cite[Definition~2.2]{Li26}}]\label[definition]{def:local}
Let $N,\kappa\ge1$. A \emph{$\kappa$-local class} $\cH$ on a domain $\cX$ assigns to every $x\in\cX$ a set
$R(x)\subseteq[N]$ with $|R(x)|\le\kappa$ and a predicate $f_x\colon\{0,1\}^{R(x)}\to\{0,1\}$, both computable in
time polynomial in $N$ and the length of $x$. A \emph{description} $w\in\{0,1\}^N$ defines
$h_w(x)=f_x(w|_{R(x)})$, and $\cH=\{h_w:w\in\{0,1\}^N\}$.
\end{definition}

\begin{example}[{\cite[Example~2.3]{Li26}}]\label[example]{ex:local}
Let $\cX_k=\{x\in\{-1,0,1\}^n:|\supp(x)|\le k\}$, and describe a sign vector $\sigma\in\{\pm1\}^n$ by the bits
$w_i=(1+\sigma_i)/2$, so that $N=n$.
\begin{enumerate}[label=(\alph*)]
\item \emph{Literal disjunctions} $\LD_k$ on $\cX_k$: $h_\sigma(x)=1$ if and only if $x_i=\sigma_i$ for some
$i\in\supp(x)$. A positive example $x$ is the clause $\bigvee_{i\in\supp(x)}(\sigma_i=x_i)$, so a sample of
positive examples is a $k$-CNF.
\item \emph{Binarized perceptrons} $\BP_k$ on $\cX_k$: $h_\sigma(x)=\ind[\langle\sigma,x\rangle\ge0]$.
\end{enumerate}
Both are $k$-local with $R(x)=\supp(x)$. Random local functions are introduced in \cref{sec:average}.
\end{example}

A \emph{sample} or \emph{context} is a sequence $S=((x_1,y_1),\dots,(x_m,y_m))$ of labeled inputs. Its
\emph{version space} is $\VS(S)=\{w:h_w(x_i)=y_i\text{ for all }i\}$, the \emph{error count} of $w$ is
$e_S(w)=|\{i:h_w(x_i)\ne y_i\}|$, and the \emph{error profile} is
$E_S(V)=\sum_{w\in\{0,1\}^N}V^{e_S(w)}$, a polynomial of degree at most $m$ whose coefficient of $V^j$ counts
the descriptions with exactly $j$ errors.

\subsection{In-context learning}\label{sec:model}

\begin{definition}[Episodes, learners and risk]\label[definition]{def:episode}
A \emph{task family} is a class $\cH=\{h_w:w\in\{0,1\}^N\}$ on $\cX$ together with a distribution $\cD$ on
$\cX$; the \emph{noise rate} is some $\eta\in[0,1/2)$. An \emph{episode} of length $m$ draws a task $w$
uniformly from $\{0,1\}^N$, inputs $x_1,\dots,x_{m+1}$ independently from $\cD$, and independent bits
$\xi_1,\dots,\xi_{m+1}$ with $\Pr[\xi_i=1]=\eta$, and sets $y_i=h_w(x_i)\oplus\xi_i$. Its \emph{context} is
$S=((x_i,y_i))_{i\le m}$, its \emph{query} is $x_{m+1}$ and its \emph{target} is $y_{m+1}$. An
\emph{in-context learner} is an algorithm $A$ that maps a context and a query to a label, possibly using
random bits. Its \emph{risk} at context length $m$ is $R_m(A)=\Pr[A(S,x_{m+1})\ne y_{m+1}]$, the probability
over the episode and the random bits of $A$.
\end{definition}

The prior is uniform on descriptions. For quantized models this is the uniform prior on parameters; the
induced prior on functions need not be uniform. Let $\mu=\eta/(1-\eta)$, with $0^0=1$.

\begin{definition}[Posterior, Bayes and Gibbs predictors]\label[definition]{def:bayes}
For a context $S$, let $\omega_S(w)=\mu^{e_S(w)}$ and $Z_S=\sum_w\omega_S(w)$. If $Z_S>0$, the
\emph{posterior} is $\pi_S(w)=\omega_S(w)/Z_S$, and the \emph{posterior predictive} of a query $x$ is
$p_S(x)=\sum_{w:h_w(x)=1}\pi_S(w)$. The \emph{Bayes in-context predictor} is
$\Bayes(S,x)=\ind[p_S(x)\ge1/2]$. The \emph{Gibbs in-context predictor} $\Gibbs(S,x)$ draws $w$ from $\pi_S$ and
outputs $h_w(x)$. \emph{Bayesian inference in context} is the problem of computing $p_S(x)$ from $S$ and $x$,
and \emph{$\beta$-approximate} Bayesian inference in context asks for a number within $\beta$ of $p_S(x)$.
\end{definition}

For $\eta=0$ the weight $\omega_S$ is the indicator of $\VS(S)$, so $Z_S>0$ exactly when the context is
consistent, and the posterior is uniform on the version space. Contexts that occur in episodes have
$Z_S>0$. In an episode, $\pi_S$ is the conditional distribution of the task given the context, by Bayes'
rule, and the conditional probability that the target is $1$ is
\begin{equation}\label{eq:phat}
\hat p_S(x)=(1-\eta)\,p_S(x)+\eta\,(1-p_S(x)).
\end{equation}
Since $\eta<1/2$, the predictor $\Bayes$ outputs the more likely target. Hence it minimizes the risk.

\begin{restatable}[Bayes decision rule]{lemma}{lembayesrule}\label[lemma]{lem:bayesrule}
For every task family, noise rate and context length $m$, every in-context learner $A$ has
$R_m(A)\ge R_m(\Bayes)$, and $R_m(\Bayes)=\mathbb E[\min\{\hat p_S(x_{m+1}),1-\hat p_S(x_{m+1})\}]$.
\end{restatable}

We write $R^*_m=R_m(\Bayes)$ for the \emph{Bayes risk}. We also use the worst-case guarantee of learning
theory.

\begin{definition}[PAC in-context learners]\label[definition]{def:pac}
An in-context learner $A$ for $\cH$ is \emph{$(\eps,\delta)$-PAC from $m$ examples} if for every
distribution $\cD$ on $\cX$ and every $w$, with probability at least $1-\delta$ over a context of $m$
independent examples $(x,h_w(x))$ with $x\sim\cD$ and over the random bits of $A$, it satisfies
$\Pr_{x\sim\cD}[A(S,x)\ne h_w(x)]\le\eps$. It is \emph{$(\eps,\delta)$-agnostic from $m$ examples} if for
every distribution $\cD'$ on $\cX\times\{0,1\}$, with probability at least $1-\delta$ over a context of $m$
independent examples from $\cD'$, it satisfies $\Pr_{(x,y)\sim\cD'}[A(S,x)\ne y]\le\opt+\eps$, where
$\opt=\min_w\Pr_{(x,y)\sim\cD'}[h_w(x)\ne y]$.
\end{definition}

An $(\eps,\delta)$-PAC learner has risk at most $\eps+\delta$ in every noiseless episode, for every input
distribution, whatever the prior. An $(\eps,\delta)$-agnostic learner has risk at most $\eta+\eps+\delta$ in
every episode with noise rate $\eta$, because for each fixed task the error of $h_w$ itself is $\eta$.

\subsection{Imported results}\label{sec:imported}

We use the refutations of ETH~\cite{OAI26,Cla26} only through the following statements of~\cite{Li26}.
Let $T_\kappa(N)=\min\{2^N,2^{C_1\kappa^2g(N)}\}$, where $g(N)=N\log\log N/\sqrt{\log N}$ for $N\ge16$, $g(N)=1$
for smaller $N$, and $C_1$ is the absolute constant of the counting algorithm of~\cite[Main Theorem and
Corollary~11]{Cla26}.

\begin{fact}[Version spaces are $\kappa$-CNFs~{\cite[Lemma~3.1]{Li26}}]\label[fact]{fact:vscnf}
Given a sample $S$ of size $m$ for a $\kappa$-local class with $N$-bit descriptions, one can compute in time
$\poly(N,m)\cdot2^\kappa$ a $\kappa$-CNF $\Gamma_S$ on the variables $w_1,\dots,w_N$ with at most $m2^\kappa$
clauses such that $\VS(S)$ is the set of satisfying assignments of $\Gamma_S$.
\end{fact}

\begin{fact}[Counting and sampling version spaces~{\cite[Theorem~3.2]{Li26}}]\label[fact]{fact:vs}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions, and let $S$ be a sample of size $m$. Then $|\VS(S)|$
can be computed deterministically in time $\poly(N,m)\cdot2^\kappa\cdot T_\kappa(N)$. If $\VS(S)\ne\emptyset$, a
uniformly random element of $\VS(S)$ can be generated exactly in the same time, given uniform random
integers in $\{0,\dots,M-1\}$ at cost $\poly(\log M)$.
\end{fact}

\begin{fact}[Error profiles~{\cite[Lemma~2.8]{Li26}}]\label[fact]{fact:profile}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions, let $S$ be a sample of size $m$, and let
$s=\max\{4\kappa m,m+1,\kappa^2\}$. The error profile $E_S$ can be computed exactly and deterministically in
time $\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$.
\end{fact}

\begin{fact}[Exponential mechanism~{\cite[Theorem~4.6]{Li26}}]\label[fact]{fact:expmech}
In the setting of \cref{fact:profile}, let $\lambda>0$. One can sample $w$ with probability proportional to
$e^{-\lambda e_S(w)}$ in time $\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$, given exact samples from explicitly
given distributions on $\{0,\dots,m\}$. Without exact sampling, the output distribution is within
statistical distance $\nu$ of the target for any $\nu\ge2^{-\poly(N,m)}$, in the same time.
\end{fact}

\Cref{fact:expmech} is~\cite[Theorem~4.6]{Li26} with privacy parameter $2\lambda$, since the score there is
$m$ times the empirical error, that is $e_S(w)$. Its algorithm samples an error count $j$ with probability proportional to
$c_je^{-\lambda j}$, where $c_j$ is the coefficient of $V^j$ in $E_S$, and then a uniform description with
exactly $j$ errors.

\begin{fact}[Perceptron gadget~{\cite[Lemma~3.3]{Li26}}]\label[fact]{fact:gadget}
Let $k\ge1$ and $p=\max\{1,k-2\}$. Given a $k$-CNF $\Gamma$ on $z_1,\dots,z_n$ with $M$ clauses, none of them
tautological, one can compute in polynomial time a sample $S_\Gamma$ of $M+p$ examples in
$\{-1,0,1\}^{n+p}$, all labeled $1$ and each with support of size at most $\max\{2k-2,2\}$, such that a sign
vector $\sigma$ is consistent with $S_\Gamma$ as a binarized perceptron if and only if
$\sigma_{n+1}=\dots=\sigma_{n+p}=1$ and the assignment $z_i=\ind[\sigma_i=1]$ satisfies $\Gamma$.
\end{fact}

\begin{fact}[Width reduction~{\cite[Corollary~3.6]{Li26}}]\label[fact]{fact:logsat}
Under \cref{hyp:cnfseth}, for every $\gamma\in(0,1)$ there are $K',c'$ such that $k$-SAT with $k\le K'\log
n$ cannot be solved in time $O(2^{(1-\gamma)n})$ by a randomized algorithm with error probability at most
$1/3$, even on instances with at most $n^{c'}$ clauses. Under \cref{hyp:cnfeth}, there are $K',c',\rho>0$
such that $k$-SAT with $k\le K'\log n$ and at most $n^{c'}$ clauses cannot be solved in time $O(2^{\rho n})$.
\end{fact}

We also use the standard sample sizes for classes of VC dimension $d$, finite or
infinite~\cite{BEHW89,SSBD14}. There are absolute constants $C_0,C_B\ge1$ such that, with probability at
least $1-\delta$ over $m$ independent examples, the following hold.

\begin{fact}[Sample sizes]\label[fact]{fact:samples}
Let $\mathcal G$ be a class of VC dimension $d\ge1$.
\begin{enumerate}[label=(\alph*)]
\item If $m\ge\mVC(d,\eps,\delta):=C_B(d\log(2/\eps)+\log(2/\delta))/\eps$ and the examples are labeled by
some $g^*\in\mathcal G$, every $g\in\mathcal G$ consistent with them has error at most $\eps$.
\item If $m\ge\mUC(d,\eps,\delta):=C_0(d+\ln(1/\delta))/\eps^2$, every $g\in\mathcal G$ has empirical error
within $\eps/2$ of its error.
\end{enumerate}
\end{fact}

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

The new algorithms need bounded clause width or linear total size, and the following hypotheses concern
the opposite regime~\cite{Li26}. All are stated for randomized algorithms with error probability at most
$1/3$.

\begin{hypothesis}[CNF-SETH]\label[hypothesis]{hyp:cnfseth}
For every $\gamma>0$ there is $c>0$ such that satisfiability of CNF formulas with $n$ variables and at most
$n^c$ clauses, of arbitrary width, cannot be decided in time $O(2^{(1-\gamma)n})$.
\end{hypothesis}

\begin{hypothesis}[CNF-ETH]\label[hypothesis]{hyp:cnfeth}
There are $c,\rho>0$ such that satisfiability of CNF formulas with $n$ variables and at most $n^c$ clauses
cannot be decided in time $O(2^{\rho n})$.
\end{hypothesis}

\begin{hypothesis}[Length form of ETH at rate $C$~{\cite[Hypothesis~2.14]{Li26}}]\label[hypothesis]{hyp:leneth}
For $C>0$, the hypothesis $\lenETH{C}$ states that no randomized algorithm decides satisfiability of every
CNF formula of length $L$ in time $2^{L/(\log L)^C}$, for all sufficiently large $L$.
\end{hypothesis}

The new algorithms decide SAT of length $L$ in time $2^{O(L/\sqrt{\log L})}$, so $\lenETH{C}$ is false for
$C<1/2$ and open for $C\ge1/2$~\cite{Li26}. It is the instance with an explicit rate of the polylog-slack
hypotheses of~\cite{CRTY23}. CNF-SETH and CNF-ETH are not contradicted by the new algorithms, and by width
reduction their hard instances may be taken to have width $O(\log n)$ (\cref{fact:logsat}). The local
pseudorandom generator hypotheses of \cref{sec:average} complete the list.