\section{The average case: random local functions}\label{sec:average}

The lower bounds of \cref{sec:hardness} concern atypical contexts. On typical episodes, the question is
whether an efficient learner can reach the Bayes risk. For random local functions it cannot, at the context
lengths where the Bayes predictor already succeeds, unless Goldreich's generator is insecure.

\subsection{Random local functions and Goldreich's generator}\label{sec:goldreich}

\begin{definition}[Random local functions]\label[definition]{def:rl}
Let $k\ge2$ and $P\colon\{0,1\}^k\to\{0,1\}$. Let $\cX^{(k)}_N$ be the set of $k$-tuples of distinct indices in
$[N]$, and let $\cD_k$ be the uniform distribution on it. The class $\RL_P$ on $\cX^{(k)}_N$ has the
hypotheses $h_w(\tau)=P(w_{\tau_1},\dots,w_{\tau_k})$ for $w\in\{0,1\}^N$. It is $k$-local with
$R(\tau)=\{\tau_1,\dots,\tau_k\}$. Goldreich's generator with $m$ outputs maps $w$ and $\tau_1,\dots,\tau_m$ to
$G_{P,m}(\tau;w)=(h_w(\tau_1),\dots,h_w(\tau_m))$~\cite{Gol00}.
\end{definition}

So an episode of the task family $(\RL_P,\cD_k)$ without noise is a run of Goldreich's generator with $m+1$
outputs: the context is the first $m$ outputs with their tuples, and the target is the last output.

Security is asymptotic: a fixed algorithm must fail for all large $N$. (For a single $N$, an algorithm that
stores the finite image of the generator distinguishes it quickly, so a statement about all algorithms of a
given running time at one $N$ would be false.)

\begin{definition}[Pseudorandomness]\label[definition]{def:prg}
Let $m=m(N)$. The \emph{advantage} of a probabilistic algorithm $A$ against $G_{P,m}$ at dimension $N$ is
\[
\mathrm{adv}_A(N)=\bigl|\Pr[A(\tau,G_{P,m}(\tau;w))=1]-\Pr[A(\tau,b)=1]\bigr|,
\]
where $\tau$ is uniform in $(\cX^{(k)}_N)^m$, $w$ is uniform in $\{0,1\}^N$, and $b$ is uniform in $\{0,1\}^m$. For
a function $T=T(N)$, the generator $G_{P,m}$ is \emph{$T$-pseudorandom} if every probabilistic algorithm whose
running time on inputs of dimension $N$ is at most $T(N)$ for all sufficiently large $N$ has advantage at most
$1/3$ at all sufficiently large $N$.
\end{definition}

A distinguisher for $G_{P,m'}$ with $m'\le m$ yields one for $G_{P,m}$ with the same advantage, because it can
ignore the last outputs: the first $m'$ outputs of $G_{P,m}$, with their tuples, are distributed as those of
$G_{P,m'}$, and a prefix of a uniform string is uniform. Pseudorandomness of random local functions is a
central hypothesis of cryptography in $\mathrm{NC}^0$; see the survey~\cite{App16}. At polynomial stretch
$m=N^s$ it needs predicates that are uncorrelated with all parities of few inputs, and for a predicate
uncorrelated with all parities of fewer than $t$ inputs, sum-of-squares and statistical-query lower bounds
support it up to stretch $N^{\Omega(t)}$~\cite{OW14,KMOW17,FPV18}. We use two forms of the hypothesis. The first,
for every $s>1$, is Assumption~1 of Daniely and Vardi~\cite{DV21}, which they use to prove the hardness of
improper PAC learning for DNF formulas, intersections of halfspaces and other classes.

\begin{hypothesis}[$\LPRG_s$]\label[hypothesis]{hyp:lprg}
For a constant $s>1$: there are $k\ge2$ and $P\colon\{0,1\}^k\to\{0,1\}$ such that $G_{P,\lceil N^s\rceil}$ is
$T$-pseudorandom for every polynomial $T$.
\end{hypothesis}

\begin{hypothesis}[$\lenLPRG{c}$]\label[hypothesis]{hyp:lenlprg}
For a constant $c>0$: there are $k\ge2$, $P\colon\{0,1\}^k\to\{0,1\}$ and $\alpha_0\ge2$ such that for every
constant $\alpha\ge\alpha_0$, the generator $G_{P,\lceil\alpha N\rceil}$ is $2^{N/(\log N)^c}$-pseudorandom.
\end{hypothesis}

The second hypothesis is the analogue of $\lenETH{C}$ for random local functions at linear stretch. Like
$\lenETH{C}$, the new algorithms refute it below rate $1/2$.

\begin{restatable}[$\lenLPRG{c}$ fails below rate $1/2$]{proposition}{proplprgfalse}\label[proposition]{prop:lprgfalse}
For every $k\ge2$, every $P$, every constant $\alpha\ge2$ and every $c<1/2$, there is a deterministic algorithm
that runs in time at most $2^{N/(\log N)^c}$ for large $N$ and has advantage at least $1-2^{-N}$ against
$G_{P,\lceil\alpha N\rceil}$ at every $N$. Hence $\lenLPRG{c}$ is false for every $c<1/2$.
\end{restatable}

\begin{proof}[Proof sketch]
Given $(\tau,z)$, decide whether the context $((\tau_j,z_j))_{j}$ is consistent with $\RL_P$, by
\cref{fact:vs} in time $\poly(N)\cdot2^{O(k^2N\log\log N/\sqrt{\log N})}$, and output $1$ if it is. Outputs of
the generator are always consistent. A uniform $z$ is consistent with probability at most
$2^N/2^{\lceil\alpha N\rceil}\le2^{-N}$, since for fixed tuples at most $2^N$ strings are images
(\cref{app:average}).
\end{proof}

For $c\ge1/2$ the new algorithms do not contradict $\lenLPRG{c}$, and before 2026 the best known
distinguishers for suitable predicates at linear stretch took time $2^{\Omega(N)}$.

\subsection{Three regimes}\label{sec:regimes}

\begin{restatable}[Three regimes for random local functions]{theorem}{thmregimes}\label{thm:regimes}
Let $k\ge2$ be a constant and $P\colon\{0,1\}^k\to\{0,1\}$. Consider the task family $(\RL_P,\cD_k)$ without
noise.
\begin{enumerate}[label=(\alph*)]
\item\label{it:rbayes} The Bayes risk is at most $N/(m+1)$, and the Bayes predictor runs in time
$\poly(m)\cdot2^{O(N\log\log N/\sqrt{\log N})}$.
\item\label{it:rlin} The learner $\Alin$ is $(\eps,\delta)$-PAC from
$\mVC(D_k(N)+1,\eps,\delta)=O((N^k\log(1/\eps)+\log(1/\delta))/\eps)$ examples and runs in time
$\poly(N,m)$.
\item\label{it:rlower} There is an absolute constant $c_*$ with the following property. For every in-context
learner $A$ and every context length $m$, there is a probabilistic algorithm $A'$ that runs in time
$T_A+c_*(m+1)k\log N$, where $T_A$ is the running time of $A$ on contexts of length $m$, and has advantage
exactly $|1/2-R_m(A)|$ against $G_{P,m+1}$. If $m=m(N)$ is computable in time polynomial in $N$, then $A'$ is a
single algorithm for all $N$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
Parts~\ref{it:rbayes} and~\ref{it:rlin} are \cref{thm:risk,thm:bayesalg,thm:regression} for this $k$-local
class. For~\ref{it:rlower}, $A'$ runs $A$ on the first $m$ outputs and the last tuple and accepts if the
prediction equals the last output. On outputs of the generator it accepts with probability $1-R_m(A)$; on
uniform bits the last bit is independent of the rest, so it accepts with probability $1/2$
(\cref{app:average}).
\end{proof}

\begin{restatable}[The three regimes under the hypotheses]{corollary}{corregimes}\label[corollary]{cor:regimes}
\begin{enumerate}[label=(\alph*)]
\item\label{it:cpoly} Assume $\LPRG_s$, with predicate $P$ of arity $k$. Let $A$ be a polynomial-time in-context
learner for $(\RL_P,\cD_k)$ and $m(N)\le\lceil N^s\rceil-1$ a context length computable in time polynomial in
$N$. Then $R_{m(N)}(A)\ge1/6$ for all sufficiently large $N$. At $m=\lceil N^s\rceil-1$ the Bayes risk is at most
$N^{1-s}$, and $\Alin$ has risk at most $\eps$ from $O(N^k\log(1/\eps)/\eps)$ examples.
\item\label{it:clen} Assume $\lenLPRG{c}$, with predicate $P$ of arity $k$ and constant $\alpha_0$. Let
$\alpha\ge\max\{\alpha_0,7\}$ be a constant and $m(N)=\lceil\alpha N\rceil-1$. Every in-context learner that runs
in time $2^{N/(\log N)^c-1}$ on contexts of length $m(N)$ has $R_{m(N)}(A)\ge1/6$ for all sufficiently large $N$,
while the Bayes predictor has risk at most $1/\alpha<1/6$ and runs in time $2^{O(N\log\log N/\sqrt{\log N})}$.
\end{enumerate}
\end{restatable}

So, at context length $\lceil\alpha N\rceil-1$, the time needed for risk below $1/6$ on random local functions has
exponent between $N/(\log N)^c$ under $\lenLPRG{c}$ and $O(N\log\log N/\sqrt{\log N})$, which is $N/\polylog N$
on both sides when $c$ is a constant at least $1/2$. The Bayes predictor of the refutations is optimal up to
polylogarithmic factors in the exponent. Between $N^s$ and $N^k$ examples the complexity is open; the
thresholds of refutation and recovery for planted constraint satisfaction problems, near $N^{t/2}$ for
predicates uncorrelated with all parities of fewer than $t$ inputs, suggest where polynomial time
begins~\cite{FPV18,KMOW17}.