\section{The locality transition}\label{sec:locality}

This section proves the first transition. Consistency for $\kappa$-local classes is $\kappa$-SAT. So it
is subexponential for slowly growing $\kappa$, and as hard as CNF-SAT at $\kappa=\Theta(\log N)$.
Throughout, $\cH$ is a $\kappa$-local class with description length $N$. Let $g(n)=n\log\log
n/\sqrt{\log n}$ for $n\ge16$ and $g(n)=1$ for $n<16$, which is nondecreasing, and let
\[
T_\kappa(N)=\min\bigl\{2^N,\ 2^{C_1\kappa^2g(N)}\bigr\}
\]
with $C_1$ from \cref{fact:claude}.

\subsection{Version spaces are \texorpdfstring{$\kappa$}{kappa}-CNFs}\label{sec:vscnf}

\begin{lemma}[Version spaces are $\kappa$-CNFs]\label[lemma]{lem:vscnf}
Given a sample $S$ of size $m$, 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)=\SAT(\Gamma_S)$.
\end{lemma}

\begin{proof}
An example $(x,y)$ rules out exactly the patterns $\alpha\in\{0,1\}^{R(x)}$ with $f_x(\alpha)\ne y$. For
each such pattern, let $C_{x,\alpha}$ be the clause on $\{w_i:i\in R(x)\}$ that is false exactly when
$w|_{R(x)}=\alpha$. Let $\Gamma_S$ be the set of all clauses $C_{x_i,\alpha}$. Then $w$ satisfies $\Gamma_S$ if
and only if $f_{x_i}(w|_{R(x_i)})=y_i$ for every $i$. Each clause has width at most $\kappa$, and
$\Gamma_S$ takes $m2^\kappa$ evaluations of predicates. The only exception is an example with
$R(x)=\emptyset$ whose constant predicate disagrees with its label. Then $\VS(S)=\emptyset$, and we
output the unsatisfiable CNF $\{(w_1),(\neg w_1)\}$.
\end{proof}

The sample defines the map $w\mapsto(h_w(x_i))_{i\le m}$. Each output bit of this map reads at most
$\kappa$ input bits, and the version space is the preimage of the label vector. \Cref{lem:vscnf} is the
encoding that~\cite[Corollary~C.2]{OAI26} uses to count, find and sample preimages of maps with constant
output locality. For constant $\kappa$, parts~\ref{it:count}--\ref{it:pac} of the next theorem are these
statements in learning terms.

\subsection{The realizable transfer theorem}\label{sec:realizable}

\begin{restatable}[Realizable transfer]{theorem}{thmrealizable}\label{thm:realizable}
Let $\cH$ be $\kappa$-local with description length $N$, and let $S$ be a sample of size $m$.
\begin{enumerate}[label=(\alph*)]
\item\label{it:count} \emph{Counting.} The number $|\VS(S)|$ can be computed deterministically in time
$\poly(N,m)\cdot2^\kappa\cdot T_\kappa(N)$.
\item\label{it:sample} \emph{Sampling.} 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)$. With fair coins only, the same bound holds for the expected time of a Las Vegas
algorithm.
\item\label{it:pac} \emph{Proper PAC learning.} For all $\eps,\delta\in(0,1)$, the class $\cH$ is
properly $(\eps,\delta)$-PAC learnable from $\lceil\mOcc\rceil$ examples by an algorithm that is
deterministic after sampling and runs in the same time.
\item\label{it:halving} \emph{Online learning.} In the realizable mistake-bound model, the halving
algorithm makes at most $N$ mistakes, and round $t$ takes time $\poly(N,t)\cdot2^\kappa\cdot
T_\kappa(N)$.
\end{enumerate}
All four run in time $\poly(N,m)\cdot2^{o(N)}$ when $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$.
\end{restatable}

\begin{proof}[Proof sketch]
\Cref{lem:vscnf} turns the version space into a $\kappa$-CNF. \Cref{fact:claude} counts its solutions in
time $2^{C_1\kappa^2g(N)}$ independently of the number of clauses, and brute force gives the bound $2^N$.
Sampling follows from counting by self-reducibility~\cite{JVV86}: fix the bits one at a time, each
with probability proportional to the number of solutions that extend the choice. Learning follows from
the Occam bound, and halving from counting the two possible version spaces. \Cref{app:locality} gives
the details.
\end{proof}

The threshold $(\log N)^{1/4}/\sqrt{\log\log N}$ is the range in which the bound of~\cite{Cla26} is
subexponential~\cite[Appendix~D]{Cla26}. The bound is uniform in $\kappa$ because its constant does not
depend on $k$.

Counting the version space is the computational core of several classical learners. These include the
halving algorithm~\cite{BF72,Lit88} and query-by-committee~\cite{SOS92,FSST97}, which needs samples from the
version space. They also include the Gibbs algorithm, which predicts with a uniformly random consistent
hypothesis.
Part~\ref{it:count} also gives the Bayes-optimal prediction under the uniform prior, which is the halving
prediction. For local classes all of these become subexponential. For constant $\kappa\ge2$,
\cref{fact:oai} gives the same conclusions in polynomial space, with $2^{O_\kappa(N\log\log
N/\sqrt{\log N})}$ in place of $T_\kappa(N)$.

Approximate counting suffices for halving~\cite{GRS93}, and hit-and-run sampling makes query-by-committee
efficient on convex version spaces~\cite{GNT05}. For local classes, approximation does not help: any
approximate count decides whether the version space is empty, which is $\kappa$-SAT by
\cref{thm:equivalence}; see also~\cite{HMP04}. So \cref{thm:realizable} is optimal up to the rate of SAT.
Gibbs learning of binary perceptrons is a classical model of statistical physics~\cite{Gyo90,SST92}, in
which the data are random and dense. When there are few examples per weight, efficient algorithms exist
there~\cite{ALS22}. SAT and \#SAT
encodings of binarized networks also serve to verify them, by counting inputs rather than
weights~\cite{NKR+18,BSS+19}, and to train them exactly~\cite{TIC+19}.

\subsection{Learning is equivalent to bounded-width SAT}\label{sec:equivalence}

The transfer theorem is tight in a strong sense: proper learning of local classes is fine-grained
equivalent to bounded-width SAT. \Cref{lem:vscnf} gives one direction. A padding gadget gives the
other.

\begin{restatable}[Perceptron gadget]{lemma}{lemgadget}\label[lemma]{lem:gadget}
Let $k\ge1$ and $p=\max\{1,k-2\}$. Given a $k$-CNF $F$ on $z_1,\dots,z_N$ with $M$ clauses, none of them
tautological, one can compute in polynomial time a sample $S_F$ 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\}$, with the following property. A
sign vector $\sigma$ is consistent with $S_F$ 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 $F$. In particular,
$|\VS_{\BP}(S_F)|=\#F$.
\end{restatable}

The smallest case shows how the gadget works. Take $k=3$ and the clause $C=z_1\vee\neg z_2\vee z_3$.
There is one padding coordinate, and the example of $C$ is $x_C=e_1-e_2+e_3+e_{N+1}$. A pinning example
$e_{N+1}$ forces $\sigma_{N+1}=1$. Then $\langle\sigma,x_C\rangle=2t-2$, where $t$ is the number of literals
of $C$ that the assignment makes true. So $x_C$ is classified positive exactly when $C$ is satisfied. In
general, a clause of width $r\ge2$ uses $r-2$ padding coordinates with entry $+1$, a unit clause uses one
padding coordinate with entry $-1$, and the same identity holds (\cref{app:locality}).

\begin{restatable}[Locality equivalence]{theorem}{thmequivalence}\label{thm:equivalence}
Let $\kappa,k\ge1$, and let $T$ and $T'$ be nondecreasing time bounds.
\begin{enumerate}[label=(\roman*)]
\item If \#$\kappa$-SAT on $n$ variables with $M$ clauses can be solved in time $T(n,M)$, then for every
$\kappa$-local class the version space of a sample of size $m$ can be counted in time
$T(N,m2^\kappa)+\poly(N,m)\cdot2^\kappa$.
\item If version spaces of $\BP_{2k}$ samples of size $m$ in dimension $n$ can be counted
(respectively, decided nonempty) in time $T'(n,m)$, then \#$k$-SAT (respectively, $k$-SAT) on $N$
variables with $M$ clauses can be solved in time $T'(N+k,M+k)+\poly(N,M)$.
\item If $\BP_{2k}$ in dimension $n$ has a proper $(\eps,1/3)$-PAC learner that runs in time
$T'(n,1/\eps)$, then $k$-SAT on $N$ variables with $M$ clauses has a randomized algorithm with
one-sided error that runs in time $T'(N+k,\,2(M+k))\cdot\poly(N,M)$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
Part (i) is \cref{lem:vscnf}. For (ii), delete tautological clauses and apply \cref{lem:gadget}. For
(iii), run the learner on the uniform distribution over the $M+p$ examples of $S_F$ with accuracy
$\eps=1/(2(M+k))$. All errors are multiples of $1/(M+p)>\eps$, so an $\eps$-accurate output is consistent
with every example and encodes a satisfying assignment, which we check (\cref{app:locality}).
\end{proof}

Up to a factor $2$ in the locality and an additive $k$ in the dimension, the exponential-time
complexity of consistency and of proper learning to inverse-polynomial accuracy for $\kappa$-local
classes \emph{is} that of $\kappa$-SAT. So any improvement for $k$-SAT, in the rate or in the dependence on
$k$, transfers verbatim to \cref{thm:realizable}, and any improvement for learning transfers back to
$k$-SAT.

\subsection{Hardness at logarithmic locality}\label{sec:barrier}

Bounded-width SAT is subexponential, but SAT with clauses of width $\Theta(\log n)$ is as hard as CNF-SAT
with polynomially many clauses. The tool is the width reduction of Schuler~\cite{Sch05}, in the
form of Calabro, Impagliazzo and Paturi~\cite{CIP06} that preserves solution counts. We need it with
explicit constants.

\begin{restatable}[Width-reduction transfer]{lemma}{lemwidthred}\label[lemma]{lem:widthred}
Let $\rho\in(0,1]$, $c\ge1$, $K_0=2(c+1)/\rho$ and $K'=2K_0$. Suppose that $k$-SAT (respectively,
\#$k$-SAT) on $n$ variables with $k\le K'\log n$ and at most $n^{2c}$ clauses can be solved in time
$O(2^{\rho n})$ with error probability at most $1/3$. Then CNF-SAT (respectively, \#CNF-SAT) on $n$
variables with at most $n^c$ clauses can be solved in time $O(2^{\rho n}\poly(n))$ with error
probability at most $1/3$.
\end{restatable}

\begin{proof}[Proof sketch]
Let $k=\lfloor K_0\log n\rfloor$. Branch on a clause wider than $k$: either replace it by its first $k$
literals, or set these $k$ literals to false. The leaves partition the solutions~\cite{CIP06}. Let
$M\le n^c$ be the number of clauses. A leaf reached with $r$ branches of the second kind has at most
$n-kr$ free variables, and at most $\binom{M+r}{r}$ leaves have this form. Solving each leaf in
time $2^{\rho(n-kr)}$ costs $\sum_r\binom{M+r}{r}2^{\rho(n-kr)}\le2^{\rho n}(1+2^{-\rho k})^{M+n/k}$,
which is $O(2^{\rho n})$ for this choice of $k$. Leaves with few variables are solved by brute force
(\cref{app:widthred}).
\end{proof}

\begin{restatable}{corollary}{corlogsat}\label[corollary]{cor:logsat}
\begin{enumerate}[label=(\alph*)]
\item 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})$, even on instances with at most $n^{c'}$
clauses. The same holds for counting under \cref{hyp:sharpcnfseth}.
\item 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{enumerate}
\end{restatable}

The same corollary limits how a future $k$-SAT algorithm can trade the dependence on $k$ against the
rate. No such limit was known for $2^{o(n)}$ algorithms; earlier results concern $k$-dependence of
$2^{(1-\Omega(1/k))n}$ algorithms~\cite{IP01,VW21}.

\begin{corollary}[The $k$-dependence of $k$-SAT algorithms]\label[corollary]{cor:kdep}
Assume \cref{hyp:cnfseth}. Let $\mu,\nu\ge0$ and $C'>0$ be constants. Suppose that a single algorithm,
given $k$ and a $k$-CNF on $n$ variables with at most $n^{c}$ clauses, runs in time
$2^{C'k^\mu n(\log\log n)^{O(1)}/(\log n)^\nu}$ for every constant $c$. Then $\mu\ge\nu$.
\end{corollary}

\begin{proof}
Take $K'$ and $c'$ from \cref{cor:logsat}(a) for $\gamma=1/2$. For $k=\lfloor K'\log n\rfloor$ and
instances with at most $n^{c'}$ clauses, the time is at most $2^{C'K'^\mu n(\log n)^{\mu-\nu}(\log\log
n)^{O(1)}}$. If $\mu<\nu$, this is $O(2^{n/2})$, which contradicts \cref{cor:logsat}(a).
\end{proof}

The bound of~\cite{Cla26} has $\mu=2$ and $\nu=1/2$. So a $k$-SAT algorithm with rate $1/\log n$, that is
$\nu=1$, must have exponent at least linear in $k$. In terms of learning, an algorithm with exponent
$k^\mu n/(\log n)^\nu$ makes learning subexponential for $\kappa\ll(\log N)^{\nu/\mu}$, and CNF-SETH caps this
threshold at $\log N$.

\begin{restatable}[Hardness at logarithmic locality]{theorem}{thmbarrier}\label{thm:barrier}
Assume \cref{hyp:cnfseth}. For every $\gamma\in(0,1)$ there are constants $K$ and $c_\gamma$ with the
following properties. No randomized algorithm decides in time $O(2^{(1-\gamma)n})$ whether a sample of
size at most $n^{c_\gamma}$ in dimension $n$ is consistent with some binarized perceptron on $\lceil
K\log n\rceil$-sparse data. No proper $(n^{-c_\gamma},1/3)$-PAC learner for $\BP_{\lceil K\log n\rceil}$
runs in time $O(2^{(1-\gamma)n})$. Under \cref{hyp:sharpcnfseth}, the same holds for counting version spaces. Under
\cref{hyp:cnfeth}, there are $K,\rho>0$ with the same statements for time $O(2^{\rho n})$.
\end{restatable}

\begin{proof}[Proof sketch]
Take a $k$-CNF with $k=\lfloor K'\log N\rfloor$ from \cref{cor:logsat}, and apply \cref{lem:gadget}. The
sample has dimension $n\le N+k$ and sparsity $2k\le K\log n$. An algorithm in time $O(2^{(1-\gamma)n})$
would solve the formula in time $O(2^{(1-\gamma/2)N})$ (\cref{app:locality}).
\end{proof}

\begin{restatable}[The data-sparsity transition]{corollary}{corsparsity}\label[corollary]{cor:sparsity}
Consider binarized perceptrons on $k$-sparse data in dimension $n$, with samples of polynomial size.
\begin{enumerate}[label=(\alph*)]
\item If $k=o((\log n)^{1/4}/\sqrt{\log\log n})$, then consistency, version-space counting, uniform
sampling, and proper PAC learning at any accuracy take time $\poly(m)\cdot2^{o(n)}$.
\item Under \cref{hyp:cnfseth}, for every $\gamma\in(0,1)$ there are $K$ and $c_\gamma$ such that for
$k\ge K\log n$, consistency and proper PAC learning to accuracy $n^{-c_\gamma}$ cannot be done in time
$O(2^{(1-\gamma)n})$. Under \cref{hyp:sharpcnfseth}, the same holds for version-space counting.
\end{enumerate}
The same dichotomy holds for literal disjunctions $\LD_k$. There, a sample of positive examples is
literally a $k$-CNF, and (b) follows from \cref{cor:logsat} without a gadget.
\end{restatable}

Part (a) holds for every class of \cref{ex:local}, with $k$ replaced by the locality. Part (b) does
not. Sparse parities are $k$-local, but their consistency problem is linear algebra over $\mathbb F_2$
and takes polynomial time. Locality makes subexponential algorithms possible. Hardness at logarithmic
locality needs predicates $f_x$ that can encode clauses, as those of $\BP$ and $\LD$ can.

\subsection{Constant accuracy moves the threshold to \texorpdfstring{$\sqrt{\log N}$}{sqrt(log N)}}\label{sec:moderate}

\Cref{thm:realizable} pays $\kappa^2\log\log N$ in the exponent because it handles every sample, and the
version space of an arbitrary sample is an arbitrary $\kappa$-CNF. A PAC learner needs only $\mVC$
examples. The engine of \cref{sec:engine} charges for the total size $\kappa m$ of the sample instead of
the number of variables. At constant accuracy this trades the factor $\kappa\log\log N$ for a constant.

\begin{restatable}[Sample-sensitive realizable learning]{theorem}{thmmoderate}\label{thm:moderate}
Let $\cH$ be $\kappa$-local with description length $N$ and VC dimension $d\ge1$, and let
$\eps,\delta\in(0,1)$. With $m=\lceil\mVC\rceil$ examples, $\cH$ is properly $(\eps,\delta)$-PAC
learnable by an algorithm that is deterministic after sampling and runs in time
\[
\poly(N,m)\cdot\exp\Bigl(O\Bigl(\frac{\kappa\,(d\log(2/\eps)+\log(2/\delta))}{\eps\sqrt{\log(2d/\eps)}}+\kappa^2\Bigr)\Bigr).
\]
For constant $\eps$ and $\delta$ the time is $2^{O(\kappa N/\sqrt{\log N}+\kappa^2)}$, which is $2^{o(N)}$
whenever $\kappa=o(\sqrt{\log N})$.
\end{restatable}

\begin{proof}[Proof sketch]
Draw the sample. With probability one it is consistent with a target, so the coefficient of $V^0$ in
its error profile is positive. Fix the bits that the sample reads one at a time, each to a value that
keeps this coefficient positive (\cref{lem:profile}). The result is consistent, and \cref{fact:samples}(b)
bounds its error. The engine runs with $s=O(\kappa m+\kappa^2)$ and $\log s\ge\log(2d/\eps)$
(\cref{app:locality}).
\end{proof}

So proper PAC learning takes time $2^{o(N)}$ whenever $\kappa\log(2/\eps)/\eps=o(\sqrt{\log N})$ and $\delta$ is
constant. At inverse-polynomial accuracy, the window $(\log N)^{1/4}\lesssim\kappa\lesssim\log N$ is the window of
$k$-SAT itself (\cref{thm:equivalence}). Its lower end is where the $k^2$ in the exponent
of~\cite{Cla26} stops giving subexponential time. Its upper end is where width reduction makes CNF-SETH
apply. At constant accuracy the subexponential range reaches $\kappa=o(\sqrt{\log N})$, and
\cref{sec:constacc} shows that there, for constant $\kappa$, the exponent $N/\polylog N$ is the truth.