\section{Proofs for Section~\ref{sec:accuracy}: the accuracy transition}\label{app:accuracy}

\subsection{Exact ERM, agnostic learning and Max-CSP}

\thmerm*

\begin{proof}[Proof of \cref{thm:erm}]
\begin{steps}
\step{1}{1} The profile $E_S$, the minimum number $j^*$ of errors, and the number $c_{j^*}$ of minimizers can
be computed in the stated time.
\pf \Cref{lem:profile} gives $E_S=\sum_jc_jV^j$, and $j^*=\min\{j:c_j\ne0\}$.

\step{1}{2} The following procedure finds a minimizer with at most $\kappa m+1$ further profile
computations. Process the bits of $R(S)$ in order, and fix each to a value for which the profile of the
descriptions that extend the current partial assignment has a nonzero coefficient at $V^{j^*}$. Set all
other bits to $0$.
\begin{steps}
\step{2}{1} At every step some value keeps the coefficient at $V^{j^*}$ nonzero.
\pf The profile before the step is the sum of the two restricted profiles, and all coefficients are
nonnegative.
\step{2}{2} The output has exactly $j^*$ errors.
\pf At the end all bits of $R(S)$ are fixed, and a nonzero coefficient at $V^{j^*}$ means that these bits
make exactly $j^*$ errors. The other bits do not affect any label.
\qedstep{2}{3}
\pf By \sref{2}{1} and \sref{2}{2}, with one profile computation per bit of $R(S)$.
\end{steps}

\step{1}{3} For constant $\kappa$ and $m=O(N)$, the time is $2^{O(N/\sqrt{\log N})}$.
\pf Then $s=O(N)$, and $x\mapsto x/\sqrt{\log x}$ is increasing for $x\ge2$.

\qedstep{1}{4}
\pf By \sref{1}{1}--\sref{1}{3} and \cref{lem:profile}.
\end{steps}
\end{proof}

\corermlen*

\begin{proof}[Proof of \cref{cor:ermlen}]
\begin{steps}
\step{1}{1} \Let $F$ be a CNF of length $L$. \Let $F'$ arise from $F$ by replacing each clause
$(\lambda_1\vee\dots\vee\lambda_r)$ with $r\ge4$ by the chain of step \xsref{1}{3} in the proof of
\cref{lem:pcp2ld}, with fresh variables, and by deleting tautological clauses. Then $F'$ is satisfiable if
and only if $F$ is, its clauses have width at most $3$, and it has at most $L$ clauses.
\pf A satisfying assignment extends to the fresh variables of each chain, and an assignment that
falsifies a clause falsifies some clause of its chain; see steps \xsref{1}{5} and \xsref{1}{6} of the
proof of \cref{lem:pcp2ld}. A clause of width $r\ge4$ yields $r-2\le r$ clauses.
\step{1}{2} The sample $S=\{(x_C,1):C\in F'\}$ consists of $m\le L$ positive examples of $\LD_3$, and it is
consistent if and only if $F$ is satisfiable.
\pf By \cref{ex:local}(a), the hypothesis $\sigma$ labels $x_C$ positive if and only if $\sigma$ satisfies $C$.
Apply \sref{1}{1}.
\step{1}{3} An algorithm as excluded in the statement decides $F$ in time
$2^{L/(\log L)^{C+\theta}}+\poly(L)<2^{L/(\log L)^C}$ for all large $L$.
\pf The function $x\mapsto x/(\log x)^{C+\theta}$ is increasing for large $x$, $m\le L$, and the reduction
takes polynomial time.
\step{1}{4} For $\kappa=3$, \cref{thm:erm} decides consistency on $m$ examples in time
$\poly(N)\cdot2^{O(m/\sqrt{\log m})}$.
\pf Here $s=\max\{12m,m+1,9\}=O(m)$ and $\log s\ge\log m$.
\qedstep{1}{5}
\pf By \sref{1}{3}, such an algorithm contradicts $\lenETH{C}$. By \sref{1}{4}, the exponents of the upper
and the lower bound differ by a factor of at most $O((\log m)^{C-1/2+\theta})$.
\end{steps}
\end{proof}

\thmagnostic*

\begin{proof}[Proof of \cref{thm:agnostic}]
\begin{steps}
\step{1}{1} With probability at least $1-\delta$, every minimizer of $\err_S$ on $m=\lceil\mUC\rceil$
examples is $\eps$-optimal.
\pf \Cref{fact:samples}(c).
\step{1}{2} \Cref{thm:erm} finds a minimizer in time $\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$ with
$s=\max\{4\kappa m,m+1,\kappa^2\}\le6\kappa m+\kappa^2$, and $\log s\ge\log(2d/\eps)\ge1$.
\pf Because $C_0\ge1$ and $\eps<1$, we have $s\ge4\kappa m\ge4d/\eps^2\ge2d/\eps\ge2$.
\step{1}{3} The time satisfies the displayed bound.
\pf By \sref{1}{2}, $s/\sqrt{\log s}\le(6\kappa m+\kappa^2)/\sqrt{\log(2d/\eps)}$, and
$m=O((d+\log(1/\delta))/\eps^2)$.
\step{1}{4} If $\kappa/\eps^2=o(\sqrt{\log N})$ and $\delta$ is constant, the time is $2^{o(N)}$.
\begin{steps}
\step{2}{1} \Case $d\ge\sqrt N$. Then $\log(2d/\eps)\ge\frac12\log N$, and the exponent is
$O(\kappa N/(\eps^2\sqrt{\log N}))+O(\kappa^2)=o(N)$.
\pf Use $d\le N$ and $\kappa^2\le(\kappa/\eps^2)^2=o(\log N)$.
\step{2}{2} \Case $d<\sqrt N$. Then the exponent is $O(\kappa\sqrt N/\eps^2)+O(\kappa^2)=o(N)$.
\pf Use $\log(2d/\eps)\ge1$ and $\kappa/\eps^2=o(\sqrt{\log N})$.
\qedstep{2}{3}
\pf The cases are exhaustive. The factor $\poly(N,m)$ is $2^{o(N)}$, because $1/\eps^2=o(\sqrt{\log N})$.
\end{steps}
\qedstep{1}{5}
\pf By \sref{1}{1}--\sref{1}{4}.
\end{steps}
\end{proof}

\cormaxcsp*

\begin{proof}[Proof of \cref{cor:maxcsp}]
\begin{steps}
\step{1}{1} \Let $\Phi'$ be the factor graph over $\Ring_{P,\ell}$ with $P=n+1$ and $\ell=M+1$ that has, for
each constraint, a factor with entry $1$ where the constraint holds and $V$ where it fails. Then
$Z(\Phi')=\sum_jc_jV^j$, where $c_j$ is the number of assignments that violate exactly $j$ constraints.
\pf Each assignment contributes $V$ to the power of its number of violations, which is at most $M<\ell$.
Each coefficient is at most $2^n<2^P$.
\step{1}{2} \Cref{thm:sumproduct} applies with $s=\max\{4kM,n+1,M+1,k^2\}$.
\pf The size is at most $kM$, $P=n+1$, $\ell=M+1$, and the arity is at most $k\le s^{1/2}$.
\step{1}{3} Max-$3$-SAT with $M\le cn$ clauses takes time $2^{O((1+c)n/\sqrt{\log n})}$.
\pf Here $s\le\max\{12cn,n+1,cn+1,9\}\le(12c+1)n+10$ and $\log s\ge\log n$. The maximum number of satisfied
clauses is $M-\min\{j:c_j\ne0\}$.
\step{1}{4} The weighted statements hold.
\pf Give a violated clause $C$ the entry $V^{\mathrm{wt}(C)}$ and take $\ell=WM+1$, which exceeds every
total violated weight. Then $s=\max\{4kM,n+1,WM+1,k^2\}$, and for Max-$3$-SAT $s\le(12c+cW+1)n+10$.
\qedstep{1}{5}
\pf By \sref{1}{1}--\sref{1}{4}.
\end{steps}
\end{proof}

\subsection{The exponential mechanism}

\thmexpmech*

\begin{proof}[Proof of \cref{thm:expmech}]
\begin{steps}
\step{1}{1} \Let $R(S)$, $n_S$ and $\mathrm{mis}(u)$ be as in the proof of \cref{lem:profile}. It suffices to sample
$u\in\{0,1\}^{R(S)}$ with probability proportional to $e^{-\epsdp \mathrm{mis}(u)/2}$ and to fill the other bits
uniformly at random.
\pf The score of $w$ is $m\cdot\err_S(w)=\mathrm{mis}(w|_{R(S)})$, and every $u$ has $2^{N-n_S}$ extensions.
\step{1}{2} The following procedure samples $u$ exactly. Compute the restricted profile
$\sum_jc'_jV^j$ with $c'_j=|\{u:\mathrm{mis}(u)=j\}|$. Sample $j$ with probability proportional to
$c'_je^{-\epsdp j/2}$. Then sample $u$ uniformly from $\{u:\mathrm{mis}(u)=j\}$: fix the bits of $R(S)$ one at a time,
each with probability proportional to the coefficient of $V^j$ in the two restricted profiles.
\pf The second stage outputs each $u$ with $\mathrm{mis}(u)=j$ with probability $1/c'_j$, by the telescoping
argument of \cref{thm:realizable}. So $u$ has probability $c'_{\mathrm{mis}(u)}e^{-\epsdp \mathrm{mis}(u)/2}/(Z'c'_{\mathrm{mis}(u)})$, where
$Z'=\sum_jc'_je^{-\epsdp j/2}$.
\step{1}{3} The mechanism is $\epsdp$-differentially private.
\pf Changing one example changes the score of every $w$ by at most $1$, and the exponential mechanism
with weights $e^{-\epsdp\cdot\mathrm{score}/2}$ for a score of sensitivity $1$ is $\epsdp$-differentially
private~\cite{MT07}.
\step{1}{4} An output distribution within statistical distance $\eta$ of the mechanism, on every
sample, is $(\epsdp,(1+e^{\epsdp})\eta)$-differentially private, and it can be produced in time
$\poly(N,m,\log(1/\eta))$ times the cost of the profiles.
\pf For neighboring samples $S,S'$ and every event $E$, with $\mu_S$ the exact mechanism,
$\Pr[E\mid S]\le\mu_S(E)+\eta\le e^{\epsdp}\mu_{S'}(E)+\eta\le e^{\epsdp}\Pr[E\mid S']+(1+e^{\epsdp})\eta$. All
probability in \sref{1}{2} can be computed to any precision in time polynomial in $N$, $m$ and the number of bits, so fair coins approximate each choice
within any desired distance.
\step{1}{5} With the stated $m$, the output is $\eps$-optimal with probability at least $1-\delta$.
\pf This is the accuracy guarantee of the exponential mechanism over a class of size at most
$2^N$~\cite{KLN+11}.
\step{1}{6} With the stated $m$, the time is as displayed.
\pf We may take $m\ge N\ge\kappa$. Then $s\le5\kappa m$ and $\log s\ge\log N$, so the exponent is
$O(\kappa m/\sqrt{\log N})$, and $\max\{1/(\eps\epsdp),1/\eps^2\}=1/(\eps\min\{\eps,\epsdp\})$. The procedure of
\sref{1}{2} uses at most $n_S+1$ profile computations (\cref{lem:profile}).
\qedstep{1}{7}
\pf By \sref{1}{1}--\sref{1}{6}.
\end{steps}
\end{proof}

\subsection{Short PCPs and constant accuracy}

\lempcpld*

\begin{proof}[Proof of \cref{lem:pcp2ld}]
\begin{steps}
\step{1}{1} \Case some seed $\tau$ has $Q_\tau=\emptyset$ and $D_\tau=0$. Then the list
$((e_1,1),(-e_1,1))$ in dimension $1$ has the required property.
\pf The seed $\tau$ rejects every proof, so $F$ is unsatisfiable by completeness. Every $\sigma$ labels
exactly one of $e_1,-e_1$ positive, so every hypothesis has error $1/2\ge2\eps_0$.

\step{1}{2} \Case no seed rejects any pattern. Then the list $((e_1,1))$ has the required property.
\pf Every proof is accepted for every seed, so $F$ is satisfiable by soundness, and $\sigma_1=1$ has error
$0$.

\step{1}{3} \Case neither of the above. \Let $S^{\mathrm{pcp}}_F$ be built as follows. For every seed $\tau$
and every pattern $\alpha$ on $Q_\tau$ with $D_\tau(\alpha)=0$, \Let $C_{\tau,\alpha}$ be the clause on the proof
variables that is false exactly at $\alpha$. Replace each $C_{\tau,\alpha}=(\lambda_1\vee\dots\vee\lambda_t)$ with
$t\ge4$ by the chain
\[
(\lambda_1\vee\lambda_2\vee\zeta_1),\ (\neg\zeta_1\vee\lambda_3\vee\zeta_2),\ \dots,\
(\neg\zeta_{t-4}\vee\lambda_{t-2}\vee\zeta_{t-3}),\ (\neg\zeta_{t-3}\vee\lambda_{t-1}\vee\lambda_t)
\]
with fresh variables $\zeta_1,\dots,\zeta_{t-3}$ for this clause, and keep clauses of width at most $3$.
Each resulting clause $C$ becomes the positive example $x_C$ of $\LD_3$, with entry $+1$ at positive and
$-1$ at negative literals, and $S^{\mathrm{pcp}}_F$ lists these examples, one entry per occurrence.
\pf In this case every seed with $Q_\tau=\emptyset$ accepts, so every clause $C_{\tau,\alpha}$ is nonempty. It
has width at most $q$ and no complementary literals, so each $x_C$ is well defined, and by
\cref{ex:local}(a) the hypothesis $\sigma$ labels $x_C$ positive if and only if $\sigma$ satisfies $C$.

\step{1}{4} The list has at most $q2^q|\Omega_F|$ entries, and its dimension is
$N\le2q2^q|\Omega_F|\le c_qL(\log L)^\beta$.
\pf There are at most $2^q|\Omega_F|$ clauses $C_{\tau,\alpha}$. Each produces at most $q$ entries and at most $q$
fresh variables, and the proof has at most $q|\Omega_F|$ positions (\cref{fact:pcp}).

\step{1}{5} If $F$ is satisfiable, then $\opt(\cD_F)=0$.
\pf Let $\pi$ be a proof that is accepted for every seed. Then $\pi$ satisfies every $C_{\tau,\alpha}$. In a
chain, pick a true literal $\lambda_j$, and put $\zeta_i=1$ for $i\le j-2$ and $\zeta_i=0$ for $i\ge j-1$. The
first clause holds by $\lambda_j$ if $j\le2$ and by $\zeta_1$ otherwise. A middle clause
$(\neg\zeta_i\vee\lambda_{i+2}\vee\zeta_{i+1})$ holds by $\neg\zeta_i$ if $i\ge j-1$, by $\zeta_{i+1}$ if $i\le j-3$, and by
$\lambda_j$ if $i=j-2$. The last clause holds by $\neg\zeta_{t-3}$ if $j\le t-2$ and by $\lambda_j$ otherwise. So
$\pi$ extends to a hypothesis with no errors.

\step{1}{6} If $F$ is unsatisfiable, then every hypothesis has error at least $2\eps_0$.
\pf Let $\sigma$ assign all $N$ variables, and let $\pi$ be its restriction to the proof positions. The
verifier rejects $\pi$ for at least $|\Omega_F|/2$ seeds. For each of them, $C_{\tau,\alpha}$ with
$\alpha=\pi|_{Q_\tau}$ is false under $\sigma$. Its chain then contains a clause that is false under $\sigma$:
if all its clauses were true while all $\lambda_j$ are false, the chain would force
$\zeta_1=\dots=\zeta_{t-3}=1$ and falsify its last clause. Distinct seeds own disjoint entries. So
$\sigma$ errs on at least $|\Omega_F|/2$ of at most $q2^q|\Omega_F|$ entries, an error of at least
$1/(q2^{q+1})=2\eps_0$.

\qedstep{1}{7}
\pf The three cases are exhaustive, and \sref{1}{1}, \sref{1}{2} and \sref{1}{4}--\sref{1}{6} give the
property in each. The verifier runs in polynomial time, $|\Omega_F|$ is polynomial in $L$, and there are
at most $2^q$ patterns per seed.
\end{steps}
\end{proof}

\thmconstacc*

\begin{proof}[Proof of \cref{thm:constacc}]
\begin{steps}
\step{1}{1} \Let the algorithm compute $S^{\mathrm{pcp}}_F$ by \cref{lem:pcp2ld} and run the learner on
$\cD_F$ for at most $T(N)$ steps, simulating each example draw in time $\polylog(L)$. If the learner
does not halt in time, the algorithm rejects. Otherwise it computes the exact error of the output $\sigma$
on $S^{\mathrm{pcp}}_F$ and accepts if and only if the error is below $2\eps_0$.

\step{1}{2} If $F$ is satisfiable, the algorithm accepts with probability at least $2/3$.
\pf By \cref{lem:pcp2ld}, $\cD_F$ is realizable. With probability at least $2/3$ the learner halts in time
with an output of error at most $\eps_0<2\eps_0$.

\step{1}{3} If $F$ is unsatisfiable, the algorithm rejects.
\pf By \cref{lem:pcp2ld}, every hypothesis has error at least $2\eps_0$.

\step{1}{4} The algorithm runs in time $T(c_qL(\log L)^\beta)\cdot\polylog(L)+\poly(L)$.
\pf By \cref{lem:pcp2ld}, $N\le c_qL(\log L)^\beta$, and $T$ is nondecreasing. A uniform entry of a list of
polynomial length takes $\polylog(L)$ time to draw.

\step{1}{5} Under $\lenETH{C}$, no realizable learner runs in time $T(N)=2^{N/(\log N)^{C+\beta+1}}$.
\pf Let $N_L=c_qL(\log L)^\beta$. Because $\log N_L\ge\log L$, we get
$T(N_L)\le2^{c_qL/(\log L)^{C+1}}$, and $T(N_L)\polylog(L)+\poly(L)<2^{L/(\log L)^C}$ for all large $L$. The
function $T$ is nondecreasing for large $N$. By \sref{1}{2}--\sref{1}{4}, such a learner would contradict
$\lenETH{C}$.

\qedstep{1}{6}
\pf By \sref{1}{2}--\sref{1}{5}. An agnostic learner is in particular a realizable one.
\end{steps}
\end{proof}

\corsatlen*

\begin{proof}[Proof of \cref{cor:satlen}]
\begin{steps}
\step{1}{1} Part (a) holds.
\begin{steps}
\step{2}{1} \Let $S$ be a sample of $m$ examples. With probability at least $1-\delta/2$, every
$w\in\VS(S)$ has error at most $\eps$.
\pf \Cref{fact:samples}(a) with $\delta/2$.
\step{2}{2} The version space is $\SAT(\Gamma_S)$ for a CNF $\Gamma_S$ of length at most $\kappa2^\kappa m$.
\pf \Cref{lem:vscnf}.
\step{2}{3} A self-reduction finds an element of $\SAT(\Gamma_S)$ with $N$ satisfiability decisions on
CNFs of length at most $\kappa2^\kappa m+N$, all correct with probability at least $1-\delta/2$.
\pf Fix $w_1,\dots,w_N$ in order: set $w_i=0$ if $\Gamma_S$ with the fixed values and $w_i=0$ as unit
clauses is satisfiable, and $w_i=1$ otherwise. In the realizable case $\SAT(\Gamma_S)\ne\emptyset$ with
probability $1$. Repeat each decision $O(\log(N/\delta))$ times and take the majority, so that each is
wrong with probability at most $\delta/(2N)$.
\qedstep{2}{4}
\pf By \sref{2}{1}--\sref{2}{3} and a union bound, the output is $\eps$-accurate with probability at least
$1-\delta$, within the stated time.
\end{steps}

\step{1}{2} Part (b) holds.
\pf \Cref{thm:constacc}.

\step{1}{3} The stated consequences hold.
\pf With the new algorithms, $T(L)=2^{3C_1L/\sqrt{\log L}}$ (\cref{sec:hyp}), and
$\kappa2^\kappa m+N=O_{\kappa,\eps,\delta}(N)$. The lower bound is \sref{1}{2} with \cref{thm:constacc}. The
transfer of exponents follows from (a) with $L=\Theta(N)$ and from (b) with $N=\Theta(L(\log L)^\beta)$.

\qedstep{1}{4}
\pf By \sref{1}{1}--\sref{1}{3}.
\end{steps}
\end{proof}

\corgapsat*

\begin{proof}[Proof of \cref{cor:gapsat}]
\begin{steps}
\step{1}{1} \Let $F$ be a CNF of length $L$, and let $S^{\mathrm{pcp}}_F$ be the list of \cref{lem:pcp2ld},
read as a multiset of clauses of width at most $3$. Its size is $n\le2c_qL(\log L)^\beta$, it is satisfiable if
$F$ is, and otherwise every assignment violates at least a $2\eps_0$ fraction of its clauses.
\pf By \cref{lem:pcp2ld}, with step \xsref{1}{4} of its proof for the size.
\step{1}{2} An algorithm as excluded in the statement decides $F$ in time
$2^{2c_qL/(\log L)^{C+1}}+\poly(L)<2^{L/(\log L)^C}$ for all large $L$.
\pf Let $n_L=2c_qL(\log L)^\beta\ge n$. The function $x\mapsto x/(\log x)^{C+\beta+1}$ is increasing for large
$x$, and $\log n_L\ge\log L$, so $n/(\log n)^{C+\beta+1}\le n_L/(\log n_L)^{C+\beta+1}\le2c_qL/(\log L)^{C+1}$ for
large $n$; for bounded $n$ the time is $O(1)$.
\qedstep{1}{3}
\pf The bound of \sref{1}{2} contradicts $\lenETH{C}$.
\end{steps}
\end{proof}

\subsection{Hardness at inverse-polynomial accuracy}

\thmaccbarrier*

\begin{proof}[Proof of \cref{thm:accbarrier}]
\begin{steps}
\step{1}{1} \Let $F$ be a $3$-CNF on $n$ variables, and \Let $F'$ be $F$ without its $t_0$ tautological
clauses. Then $F'$ has $M\le2n+2n^2+\frac43n^3<8n^3$ clauses, and a maximum assignment for $F'$ satisfies
the maximum number of clauses of $F$.
\pf Tautological clauses are always satisfied. There are at most $\binom nj2^j$ non-tautological
clauses of width $j$.
\step{1}{2} \Let $\cD$ be uniform on $\{(x_C,1):C\in F'\}$, where $x_C$ has entry $+1$ at positive and $-1$
at negative literals of $C$. Then $\err_\cD(\sigma)$ is the fraction of clauses of $F'$ that $\sigma$ violates.
\pf By \cref{ex:local}(a), $h_\sigma(x_C)=1$ if and only if $\sigma$ satisfies $C$.
\step{1}{3} Every output with $\err_\cD(\sigma)\le\opt+\eps$ is an optimal assignment for $F'$.
\pf All errors are multiples of $1/M$, and $1/M>1/(8n^3)=\eps$.
\qedstep{1}{4}
\pf By \sref{1}{1}--\sref{1}{3}, a learner in time $O(2^{(1-\gamma)n})$, with each example draw simulated in time $\poly(n)$, computes in time $O(2^{(1-\gamma)n}\poly(n))\subseteq O(2^{(1-\gamma/2)n})$ the maximum number of
satisfied clauses of $F$, namely $t_0$ plus the number of clauses of $F'$ that its output satisfies,
with error probability at most $1/3$. This contradicts \cref{hyp:maxsat} for $\gamma/2$. If $F'$ is empty, the answer is
$t_0$.
\end{steps}
\end{proof}