\section{Open problems}\label{sec:open}

\begin{problem}[Typical contexts for natural families]\label{prob:typical}
The worst-case lower bounds of \cref{thm:hardness} use atypical contexts, and the average-case bounds of
\cref{cor:regimes} use random local functions. Is Bayesian inference in context hard on typical episodes of
binarized perceptrons or literal disjunctions on sparse data, for natural input distributions, at locality
$O(\log N)$?
\end{problem}

\begin{problem}[Approximate Bayesian inference]\label{prob:approx}
Our lower bounds exclude additive error $1/4$ on all contexts. With label noise, the posterior is a Gibbs
measure at inverse temperature $\ln((1-\eta)/\eta)$. Is there a noise rate below which approximating the
posterior predictive becomes easy, for example by Markov chain methods, and does the threshold depend on the
locality?
\end{problem}

\begin{problem}[Between $N^s$ and $N^k$ examples]\label{prob:middle}
For random local functions of arity $k$, polynomial-time learning needs more than $N^s$ examples under
$\LPRG_s$ and succeeds from $O(N^k)$. What is the time needed from $N^{1+\beta}$ examples, as a function of
$\beta$? Spectral refutation trades density for time on random instances; can it be combined with the
algorithms of the refutation of ETH to beat $2^{N/\sqrt{\log N}}$ at superlinear context length?
\end{problem}

\begin{problem}[The locality window]\label{prob:window}
By \cref{thm:bayesequiv}, the complexity of exact Bayesian inference in context at locality between $(\log
N)^{1/4}$ and $K\log N$ is that of $\#k$-SAT for $k=(\log N)^{\Theta(1)}$, the window of~\cite[Open
Problem~1]{Li26}. Is approximate Bayesian inference in context easier there than exact counting?
\end{problem}

\begin{problem}[Bayes risk without Bayes inference]\label{prob:risk}
For binarized perceptrons on $(K\log N)$-sparse data, $\Alp$ has risk $O(N\log m/m)$ and the Bayes risk is at
most $N/(m+1)$. Can a polynomial-time in-context learner achieve risk $R^*_m+\eps$ for every input
distribution and every $\eps>0$, with $m$ polynomial in $N/\eps$, or is the Bayes risk itself hard to reach for
this family?
\end{problem}