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

Counting is not enough for agnostic learning. An agnostic learner must find a hypothesis with the
fewest errors, and a private learner must weigh every hypothesis by its error. Both tasks need the
error profile, which the engine computes exactly (\cref{lem:profile}). This section turns the profile
into learners. It then shows that the accuracy decides which form of SAT governs learning: SAT by
formula length at constant accuracy, and Max-3-SAT at inverse-polynomial accuracy. Throughout,
$\cH$ is $\kappa$-local with description length $N$.

\subsection{Exact ERM and proper agnostic learning}\label{sec:agnostic}

\begin{restatable}[Exact ERM]{theorem}{thmerm}\label{thm:erm}
For a $\kappa$-local class and any sample $S$ of size $m$, a minimizer of $\err_S$, the number of
minimizers and the entire error profile can be computed in time $\poly(N,m)\cdot2^{O(s/\sqrt{\log
s})}$, where $s=\max\{4\kappa m,m+1,\kappa^2\}$. In particular, for constant $\kappa$ and $m=O(N)$, exact
ERM takes time $2^{O(N/\sqrt{\log N})}$.
\end{restatable}

\begin{proof}[Proof sketch]
\Cref{lem:profile} gives the profile, and its lowest nonzero coefficient gives the minimum number $j^*$
of errors. To find a minimizer, fix the bits that the sample reads one at a time, each to a value for
which the profile of the restricted descriptions still has a nonzero coefficient at $V^{j^*}$. Such a
value exists, because the profile is the sum of the profiles of the two restrictions
(\cref{app:accuracy}).
\end{proof}

For $3$-local classes the engine is optimal up to polylogarithmic factors in the exponent, already for
consistency. The reason is that a CNF is a sample of positive examples of literal disjunctions.

\begin{restatable}[Consistency is SAT by length]{corollary}{corermlen}\label[corollary]{cor:ermlen}
Assume $\lenETH{C}$, and let $\theta>0$. No randomized algorithm with error probability at most $1/3$
decides in time $2^{m/(\log m)^{C+\theta}}$ whether a sample of $m$ positive examples of $\LD_3$ is
consistent. So for $3$-local classes, \cref{thm:erm} is optimal up to a factor $(\log m)^{C-1/2+\theta}$ in the
exponent.
\end{restatable}

\begin{proof}[Proof sketch]
Split the clauses of a CNF of length $L$ into clauses of width at most $3$ with fresh variables. The result
has at most $L$ clauses, and each clause is a positive example of $\LD_3$ (\cref{ex:local}(a)). So $m\le L$,
and the sample is consistent if and only if the CNF is satisfiable (\cref{app:accuracy}).
\end{proof}

\begin{restatable}[Agnostic transfer]{theorem}{thmagnostic}\label{thm:agnostic}
Let $\cH$ be $\kappa$-local with description length $N$ and VC dimension $d$, and let
$\eps,\delta\in(0,1)$. Exact ERM on $m=\lceil\mUC\rceil$ examples is a proper $(\eps,\delta)$-agnostic
learner, and it runs deterministically after sampling in time
\[
\poly(N,m)\cdot\exp\Bigl(O\Bigl(\frac{\kappa(d+\log(1/\delta))}{\eps^2\sqrt{\log(2d/\eps)}}+\kappa^2\Bigr)\Bigr).
\]
If $\kappa/\eps^2=o(\sqrt{\log N})$ and $\delta$ is constant, the time is $2^{o(N)}$.
\end{restatable}

\begin{proof}[Proof sketch]
By \cref{fact:samples}(c), every minimizer of $\err_S$ is $\eps$-optimal with probability at least
$1-\delta$. \Cref{thm:erm} finds one with $s=O(\kappa m+\kappa^2)$, and $s\ge4\kappa m\ge2d/\eps$ gives
$\log s\ge\log(2d/\eps)$ (\cref{app:accuracy}).
\end{proof}

This bound depends on the VC dimension through $d/\eps^2$, not on $N$. For local classes whose
descriptions are much longer than their VC dimension, the learner is polynomial in $N$ and
subexponential in $d/\eps^2$.

The proof of \cref{thm:erm} never uses that the constraints come from a hypothesis class. It solves
sparse Max-CSP exactly, and this refutes a hypothesis from fine-grained approximability.

\begin{restatable}[Sparse Max-CSP]{corollary}{cormaxcsp}\label[corollary]{cor:maxcsp}
Let $\Phi$ be a Boolean constraint system on $n$ variables with $M$ constraints of arity at most $k$.
For every $j$, the number of assignments that violate exactly $j$ constraints can be computed in time
$\poly(n,M)\cdot2^{O(s/\sqrt{\log s})}$, where $s=\max\{4kM,n+1,M+1,k^2\}$. In particular, for every
constant $c$, Max-$3$-SAT with $n$ variables and at most $cn$ clauses can be solved in time
$2^{O((1+c)n/\sqrt{\log n})}$. With positive integer clause weights at most $W$, the same holds with
$s=\max\{4kM,n+1,WM+1,k^2\}$, and Max-$3$-SAT takes time $2^{O((1+cW)n/\sqrt{\log n})}$.
\end{restatable}

\begin{corollary}\label[corollary]{cor:sparsemaxsat}
Both Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams (\cref{hyp:sparsemaxsat}) are false.
\end{corollary}

\begin{proof}
Let $c>0$. By \cref{cor:maxcsp}, Max-3-SAT and Max-2-SAT with $cn$ clauses can be solved
deterministically in time $2^{O((1+c)n/\sqrt{\log n})}$. This is $O(2^{n/2})$, and $1/2<1-\gamma$ and
$1/2<\omega/3-\gamma$ for $\gamma=1/10$, because $\omega\ge2$. So for $\gamma=1/10$ no $c$ satisfies either
requirement of \cref{hyp:sparsemaxsat}.
\end{proof}

Before 2026, the best algorithms for Max-SAT with $cn$ clauses saved a factor $2^{n/O(c^{1/3}\log^{7/3}c)}$
over brute force~\cite{ACW16}, and Max-2-SAT took time $2^{\omega n/3}$~\cite{Wil05}. Alman and Vassilevska
Williams~\cite{AVW20} posed \cref{hyp:sparsemaxsat} as a basis for lower bounds on OV graphs.
Bringmann, Cassis, Fischer and K\"unnemann~\cite{BCFK22} showed that the sparse Max-3-SAT hypothesis
implies all hardness results of their fine-grained approximability classification. Most of those results
also follow from hypotheses about clique detection in hypergraphs~\cite{BCFK22}, which the new
algorithms do not affect. \Cref{cor:sparsemaxsat} also follows from Theorem~1.1 of~\cite{OAI26}. One applies it to a CNF encoding of
a linear-size threshold circuit for the number of satisfied clauses, as in the proof of its
Corollary~1.2.
The error profile gives it directly, together with the number of optimal assignments and the whole
distribution of the number of violated clauses.

\subsection{The exact exponential mechanism}\label{sec:expmech}

The profile also gives the exponential mechanism of McSherry and Talwar~\cite{MT07} exactly, and with
it the generic private learner of Kasiviswanathan et al.~\cite{KLN+11}.

\begin{restatable}[Exact private learning]{theorem}{thmexpmech}\label{thm:expmech}
Let $\cH$ be $\kappa$-local and $\epsdp>0$. On a sample $S$ of size $m$, one can sample $w$ with
probability proportional to $\exp(-\epsdp\,m\,\err_S(w)/2)$ in time
$\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$, where $s=\max\{4\kappa m,m+1,\kappa^2\}$, given exact samples
from explicitly given distributions on $\{0,\dots,m\}$. This is the exponential mechanism, and it is
$\epsdp$-differentially private. Without exact sampling, the output distribution is within statistical
distance $\eta$ of the mechanism for any $\eta\ge2^{-\poly(N,m)}$, and the output is
$(\epsdp,(1+e^{\epsdp})\eta)$-differentially private. With
$m=O\bigl((N+\log(1/\delta))\max\{1/(\eps\epsdp),1/\eps^2\}\bigr)$, the output is $\eps$-optimal with
probability at least $1-\delta$~\cite{KLN+11}, and the time is, up to polynomial factors,
\[
\exp\Bigl(O\Bigl(\frac{\kappa\,(N+\log(1/\delta))}{\eps\min\{\eps,\epsdp\}\sqrt{\log N}}\Bigr)\Bigr).
\]
\end{restatable}

\begin{proof}[Proof sketch]
Descriptions that agree on the bits read by the sample have the same score. So it suffices to sample an
error count $j$ with probability proportional to $c_je^{-\epsdp j/2}$, then a uniform description with
exactly $j$ errors, by self-reduction on the restricted profiles (\cref{app:accuracy}).
\end{proof}

So for local classes the exponential mechanism over the whole class, the canonical but inefficient
generic private learner, runs in time $2^{o(N)}$ when $\kappa/(\eps\min\{\eps,\epsdp\})=o(\sqrt{\log N})$
and $\log(1/\delta)=O(N)$. Its output distribution is the Gibbs posterior at inverse temperature
$\epsdp/2$. So \cref{thm:expmech} is also exact posterior sampling over discrete weights, and one posterior
sample is differentially private~\cite{WFS15}. Implementations of the exponential mechanism without the
loss $\eta$ are studied in~\cite{Ilv20,CKS20}. The time grows with the sample size, and private sample
complexity can be much smaller than $N$~\cite{BNS13}. The polynomial-time barriers for private
learning~\cite{DNR+09,Ull16,BZ16} are not affected by subexponential algorithms.

\subsection{Constant accuracy is SAT by length}\label{sec:constacc}

At constant accuracy the parameter that governs learning changes. Exact consistency is SAT
parameterized by the number of variables (\cref{thm:equivalence}). Constant-accuracy learning is SAT
parameterized by the \emph{length} of the formula. In one direction the bridge is the Occam bound. In the
other it is a probabilistically checkable proof of quasi-linear size.

\begin{fact}[Short PCPs~\cite{Din07,BS08}]\label[fact]{fact:pcp}
There are absolute constants $q$, $\beta$ and $c_V$ and a deterministic polynomial-time verifier with
the following behavior on a CNF $F$ of length $L\ge2$. The verifier picks a seed $\tau$ uniformly from a
set $\Omega_F$ of size at most $c_VL(\log L)^\beta$. From $F$ and $\tau$ it computes a set $Q_\tau$ of at
most $q$ positions of a proof $\pi$ of length at most $q|\Omega_F|$, and a predicate $D_\tau$ on these
positions. It accepts if and only if $D_\tau(\pi|_{Q_\tau})=1$. If $F$ is satisfiable, some proof is
accepted for every seed. If $F$ is unsatisfiable, every proof is rejected for at least half of the
seeds.
\end{fact}

Dinur~\cite{Din07} proves $\mathrm{SAT}\in\mathrm{PCP}_{1/2,1}[\log(n\,\polylog n),O(1)]$ by gap
amplification of the PCPs of Ben-Sasson and Sudan~\cite{BS08}, where $n$ is the input bit length. For a
CNF of length $L$ we have $n=O(L\log L)$, and $\beta$ absorbs the difference. Her verifier reads $O(1)$
symbols over a constant alphabet. Reading their binary encodings gives the non-adaptive form above,
and deleting unqueried positions bounds the proof length.

\begin{restatable}[Short PCPs as $\LD_3$ samples]{lemma}{lempcpld}\label[lemma]{lem:pcp2ld}
Let $\eps_0=1/(q2^{q+2})$ and $c_q=2q2^qc_V$. There is a deterministic polynomial-time reduction that
maps a CNF $F$ of length $L\ge2$ to a list $S^{\mathrm{pcp}}_F$ of positive examples of $\LD_3$ in
dimension $N\le c_qL(\log L)^\beta$, with the following property. Let $\cD_F$ be the uniform
distribution over the entries of $S^{\mathrm{pcp}}_F$. If $F$ is satisfiable, then $\opt(\cD_F)=0$. If $F$
is unsatisfiable, then $\opt(\cD_F)\ge2\eps_0$.
\end{restatable}

\begin{proof}[Proof sketch]
Every rejected pattern of every seed becomes a clause of width at most $q$ on the proof bits. A chain of
fresh variables splits this clause into clauses of width $3$, and each $3$-clause becomes a positive
example of $\LD_3$ (\cref{ex:local}(a)). A proof that the verifier always accepts extends to an
assignment that satisfies every chain. If $F$ is unsatisfiable, every assignment falsifies, for at
least half of the seeds, some clause in the chain of that seed. Each seed contributes at most $q2^q$
entries, which gives the gap $2\eps_0$ (\cref{app:accuracy}).
\end{proof}

\begin{restatable}[Hardness at constant accuracy]{theorem}{thmconstacc}\label{thm:constacc}
If $\LD_3$ has a proper realizable $(\eps_0,1/3)$-PAC learner that runs in time $T(N)$, with $T$
nondecreasing, then satisfiability of CNF formulas of length $L$ can be decided with one-sided error
$1/3$ in time $T(c_qL(\log L)^\beta)\cdot\polylog(L)+\poly(L)$. Consequently, under $\lenETH{C}$, no
proper realizable $(\eps_0,1/3)$-PAC learner for $\LD_3$, and so no proper $(\eps_0,1/3)$-agnostic
learner, runs in time $2^{N/(\log N)^{C+\beta+1}}$.
\end{restatable}

\begin{proof}[Proof sketch]
Run the learner on $\cD_F$ with a clock, and accept if and only if it outputs, in time, a hypothesis with
error below $2\eps_0$ on $S^{\mathrm{pcp}}_F$. \Cref{lem:pcp2ld} makes this correct. A time bound
$2^{N/(\log N)^{C+\beta+1}}$ at $N\le c_qL(\log L)^\beta$ gives $2^{L/(\log L)^C}$ for SAT
(\cref{app:accuracy}).
\end{proof}

For realizable learning the Occam bound gives the converse, so the two problems have the same
complexity up to polylogarithmic factors in the exponent.

\begin{restatable}[Constant accuracy is SAT by length]{corollary}{corsatlen}\label[corollary]{cor:satlen}
Fix a constant $\kappa\ge3$, and let $T$ and $T'$ be nondecreasing.
\begin{enumerate}[label=(\alph*)]
\item If satisfiability of CNF formulas of length $L$ can be decided in time $T(L)$ with error at most
$1/3$, then every $\kappa$-local class is properly $(\eps,\delta)$-PAC learnable in time
$O(N\log(N/\delta))\cdot T(\kappa2^\kappa m+N)+\poly(N,m)$, where $m=\lceil(N\ln2+\ln(2/\delta))/\eps\rceil$.
\item Conversely, a proper realizable $(\eps_0,1/3)$-PAC learner for $\LD_3$ that runs in time $T'(N)$
decides satisfiability of CNF formulas of length $L$ in time
$T'(c_qL(\log L)^\beta)\cdot\polylog(L)+\poly(L)$.
\end{enumerate}
With the new algorithms, (a) gives time $2^{O_{\kappa,\eps,\delta}(N/\sqrt{\log N})}$. Under
$\lenETH{C}$, (b) gives the lower bound $2^{N/(\log N)^{C+\beta+1}}$ for every $\eps\le\eps_0$. A SAT
algorithm with exponent $L/f(L)$ yields learners with exponent $O(N/f(\Theta(N)))$, and a learner with
exponent $N/f(N)$ yields SAT algorithms with exponent $O(L(\log L)^\beta/f(\Theta(L(\log L)^\beta)))$.
\end{restatable}

So at a constant accuracy $\eps\le\eps_0$, the exponent of proper learning of $\LD_3$, realizable or
agnostic, lies between $N/(\log N)^{C+\beta+1}$ under $\lenETH{C}$ (\cref{thm:constacc}) and
$O(N/\sqrt{\log N})$ (\cref{thm:agnostic}). Both bounds are $N/\polylog N$. The same reduction replaces
Gap-ETH.

\begin{restatable}[Gap-3-SAT under $\lenETH{C}$]{corollary}{corgapsat}\label[corollary]{cor:gapsat}
Assume $\lenETH{C}$. No randomized algorithm with error probability at most $1/3$ runs in time
$2^{n/(\log n)^{C+\beta+1}}$ and distinguishes satisfiable $3$-CNF clause multisets from those in which
every assignment violates at least a $2\eps_0$ fraction of the clauses. Here $n$ is the number of
variables plus the number of clauses, and no bound on the number of occurrences of a variable is
assumed.
\end{restatable}

Consider a lower bound proved from Gap-ETH by a reduction of size $O(n)$ that works for every constant
gap and accepts such instances. Under $\lenETH{C}$ it holds with exponent $n/(\log n)^{C+\beta+1}$ in place of
$\Omega(n)$. A reduction with larger blowup loses correspondingly more. The route from ETH to gap hardness
through nearly-linear PCPs is standard~\cite{DKM19,GKMR21,Man23,BMVY25}. Since the refutation, Manurangsi
takes this route from Almost-ETH~\cite{Man26}, which gives only bounds of the form $2^{n^{1-\gamma}}$. The point
of \cref{cor:gapsat} is that $\lenETH{C}$ gives $2^{n/\polylog n}$, which matches the learners of
\cref{thm:agnostic}.

\subsection{Hardness at inverse-polynomial accuracy}\label{sec:accbarrier}

At inverse-polynomial accuracy, proper agnostic learning is as hard as exact ERM on a sample of
polynomial size. In that regime the Max-3-SAT Hypothesis applies, and the exponent jumps to
$(1-o(1))N$.

\begin{restatable}[Hardness at inverse-polynomial accuracy]{theorem}{thmaccbarrier}\label{thm:accbarrier}
Assume \cref{hyp:maxsat}. For every $\gamma>0$, no randomized proper $(\eps,1/3)$-agnostic learner for
$\LD_3$ in dimension $n$ with $\eps=1/(8n^3)$ runs in time $O(2^{(1-\gamma)n})$.
\end{restatable}

\begin{proof}[Proof sketch]
Remove tautological clauses from a $3$-CNF. Each of the $M<8n^3$ remaining clauses becomes a positive
example of $\LD_3$, and the error of $\sigma$ under the uniform distribution is the fraction of clauses that
$\sigma$ violates. All errors are multiples of $1/M>\eps$, so an $\eps$-optimal output is an optimal
assignment (\cref{app:accuracy}).
\end{proof}

For $3$-local classes, \cref{thm:erm} solves exact ERM on samples of size $m=o(N\sqrt{\log N})$ in time
$2^{o(N)}$. Under \cref{hyp:maxsat}, exact ERM on samples of size $\Theta(N^3)$ needs time $2^{(1-o(1))N}$.
Approximate ERM is unaffected, because one can subsample to size $O(N/\eps^2)$. Exact optimization,
however, becomes harder as the sample grows. This complements the phenomenon of Daniely, Linial and
Shalev-Shwartz~\cite{DLSS13}, where more data makes \emph{improper} learning easier.