\section{Proofs for Section~\ref{sec:locality}: the locality transition}\label{app:locality} \subsection{Realizable transfer} \thmrealizable* \begin{proof}[Proof of \cref{thm:realizable}] \begin{steps} \step{1}{1} For every $\kappa$-CNF $\Gamma$ on $w_1,\dots,w_N$ with $M'$ clauses, the number $\#\Gamma$ can be computed deterministically in time $\poly(N,M')\cdot2^\kappa\cdot T_\kappa(N)$. \begin{steps} \step{2}{1} \Let $N'$ be the number of variables that occur in $\Gamma$. Then $\#\Gamma=2^{N-N'}\cdot\#'\Gamma$, where $\#'\Gamma$ counts the satisfying assignments of the occurring variables. \pf Each variable that does not occur doubles the count. \step{2}{2} \Case $N'<16$ or $M'\le1$. Brute force over $2^{N'}$ assignments computes $\#'\Gamma$ in time $\poly(N,M')\cdot2^{\max\{16,\kappa\}}$. \pf If $M'\le1$, all occurring variables lie in one clause, so $N'\le\kappa$. \step{2}{3} \Case $N'\ge16$ and $M'\ge2$. Then $\#'\Gamma$ can be computed in time $\poly(N,M')\cdot T_\kappa(N)$. \pf \Cref{fact:claude} with $k=\kappa$ and $n=N'\ge4$ takes time at most $2^{C_1\kappa^2g(N')}\le2^{C_1\kappa^2g(N)}$, because $g$ is nondecreasing. Brute force takes time $2^{N'}\poly(M')\le2^N\poly(M')$. Run the faster of the two. \qedstep{2}{4} \pf The two cases are exhaustive. Combine them with \sref{2}{1}. \end{steps} \step{1}{2} Part~\ref{it:count} holds. \pf Build $\Gamma_S$ by \cref{lem:vscnf}, with $M'\le m2^\kappa$ clauses, and apply \sref{1}{1}. \step{1}{3} Part~\ref{it:sample} holds. \begin{steps} \step{2}{1} \Let the algorithm fix $w_1,\dots,w_N$ in order. If $w_1,\dots,w_{i-1}$ are fixed to $b_1,\dots,b_{i-1}$, it computes, for $b\in\{0,1\}$, the number $c_b$ of elements of $\VS(S)$ that extend $(b_1,\dots,b_{i-1},b)$, and it sets $w_i=b$ with probability $c_b/(c_0+c_1)$. \step{2}{2} Each count $c_b$ takes time $\poly(N,m)\cdot2^\kappa\cdot T_\kappa(N)$. \pf The count $c_b$ is $\#\Gamma$ for $\Gamma_S$ plus at most $N$ unit clauses, which is a $\kappa$-CNF because $\kappa\ge1$. Apply \sref{1}{1}. \step{2}{3} Every $w\in\VS(S)$ is output with probability $1/|\VS(S)|$. \pf The probability is a telescoping product of the ratios $c_{w_i}/(c_0+c_1)$, whose first denominator is $|\VS(S)|$ and whose last numerator is $1$. \qedstep{2}{4} \pf By \sref{2}{2} and \sref{2}{3}, with $2N$ counts. The choice of $w_i$ takes one uniform integer $U$ below $c_0+c_1\le2^N$, and sets $w_i=0$ if and only if $U0$; the result lies in $\VS(S)$. By \cref{fact:samples}(a), its error is at most $\eps$ with probability at least $1-\delta$. \step{1}{5} Part~\ref{it:halving} holds. \pf In round $t$, with the examples $S_{t-1}$ of earlier rounds, compute $c_b=|\VS(S_{t-1}\cup\{(x_t,b)\})|$ for $b\in\{0,1\}$ by part~\ref{it:count}, and predict a label $b$ with the larger count. After a mistake the version space keeps at most half of its elements. It starts with at most $2^N$ elements, and in the realizable model it never becomes empty. So there are at most $N$ mistakes. \step{1}{6} If $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$, then $2^\kappa\cdot T_\kappa(N)=2^{o(N)}$. \pf Here $\kappa^2g(N)/N=\kappa^2\log\log N/\sqrt{\log N}=o(1)$, and $\kappa=o(N)$. \qedstep{1}{7} \pf By \sref{1}{2}--\sref{1}{6}. \end{steps} \end{proof} \subsection{The perceptron gadget and the equivalence} \lemgadget* \begin{proof}[Proof of \cref{lem:gadget}] \begin{steps} \step{1}{1} \Let the coordinates $1,\dots,N$ be \emph{variable coordinates} and $N+1,\dots,N+p$ \emph{padding coordinates}. \Let $S_F$ consist of the \emph{pinning examples} $e_{N+j}$ for $j\le p$ and, for each clause $C$ with $r=|C|$ literals, the example $x_C$ defined as follows. On the variable coordinates, $x_C$ has entry $+1$ at $i$ if $z_i\in C$, entry $-1$ if $\neg z_i\in C$, and $0$ elsewhere. On the padding coordinates, $x_C$ has entry $+1$ at $N+1,\dots,N+r-2$ if $r\ge2$, entry $-1$ at $N+1$ if $r=1$, and $0$ elsewhere. All labels are $1$. \pf The clause is not tautological, so its $r$ literals are on $r$ distinct variables, and $x_C$ is well defined. It uses at most $\max\{1,k-2\}=p$ padding coordinates. \step{1}{2} Every example has support of size at most $\max\{2k-2,2\}$. \pf A clause of width $r\ge2$ gives support $r+(r-2)\le2k-2$, a clause of width $1$ gives support $2$, and a pinning example has support $1$. \step{1}{3} A pinning example $e_{N+j}$ is consistent with $\sigma$ if and only if $\sigma_{N+j}=1$. \pf Its label is $1$ and $\langle\sigma,e_{N+j}\rangle=\sigma_{N+j}$. \step{1}{4} \Assume $\sigma_{N+1}=\dots=\sigma_{N+p}=1$. \Let $z_i=\ind[\sigma_i=1]$, and \Let $t$ be the number of literals of $C$ that $z$ makes true. \Prove $\langle\sigma,x_C\rangle=2t-2$. \pf On a variable coordinate of $C$, the product of the entry of $x_C$ and $\sigma_i$ is $+1$ for a true literal and $-1$ for a false one, so the variable part is $t-(r-t)=2t-r$. The padding part is $r-2$: it is a sum of $r-2$ ones if $r\ge2$, and it is $-1=r-2$ if $r=1$. \qedstep{1}{5} \pf By \sref{1}{3} and \sref{1}{4}, $\sigma$ is consistent with $S_F$ if and only if its padding is pinned and $2t-2\ge0$, that is $t\ge1$, for every clause. This means that $z$ satisfies $F$. The map from pinned $\sigma$ to $z$ is a bijection onto $\{0,1\}^N$, so $|\VS_{\BP}(S_F)|=\#F$. The construction takes polynomial time, and \sref{1}{2} bounds the supports. \end{steps} \end{proof} \thmequivalence* \begin{proof}[Proof of \cref{thm:equivalence}] \begin{steps} \step{1}{1} Part (i) holds. \pf \Cref{lem:vscnf} builds the $\kappa$-CNF $\Gamma_S$ on $N$ variables with at most $m2^\kappa$ clauses in time $\poly(N,m)\cdot2^\kappa$, and $|\VS(S)|=\#\Gamma_S$. The assumed algorithm counts it in time $T(N,m2^\kappa)$, because $T$ is nondecreasing. \step{1}{2} Part (ii) holds. \pf Let $F$ be a $k$-CNF on $N$ variables with $M$ clauses. Deleting tautological clauses changes neither $\#F$ nor satisfiability. \Cref{lem:gadget} gives a sample of at most $M+k$ examples in dimension $N+p\le N+k$, with supports of size at most $\max\{2k-2,2\}\le2k$, whose version space has size $\#F$. Count it, or decide whether it is nonempty, in time $T'(N+k,M+k)$. \step{1}{3} Part (iii) holds. \begin{steps} \step{2}{1} \Let $F$ be a $k$-CNF on $N$ variables with $M$ clauses, without tautological clauses, and \Let $S_F$ be the sample of \cref{lem:gadget}, with $M+p\le M+k$ examples. \Let $\cD$ be the uniform distribution on $S_F$. Run the learner on $\cD$ with $\eps=1/(2(M+k))$, simulating each example draw in polynomial time, for at most $T'(N+k,2(M+k))$ steps. If it does not halt in time, reject; otherwise check whether the output encodes a satisfying assignment. \step{2}{2} If $F$ is satisfiable, the algorithm accepts with probability at least $2/3$. \pf By \cref{lem:gadget}, $\cD$ is realizable. With probability at least $2/3$, the output $\sigma$ has $\err_\cD(\sigma)\le\eps<1/(M+p)$. Errors under $\cD$ are multiples of $1/(M+p)$, so $\sigma$ is consistent with every example, and by \cref{lem:gadget} it encodes a satisfying assignment. \step{2}{3} If $F$ is unsatisfiable, the algorithm rejects. \pf No assignment passes the check. \qedstep{2}{4} \pf By \sref{2}{2} and \sref{2}{3}, the error is one-sided. The learner runs in dimension $N+p\le N+k$ with $1/\eps=2(M+k)$, and each step costs at most $\poly(N,M)$ for the simulation. \end{steps} \qedstep{1}{4} \pf By \sref{1}{1}--\sref{1}{3}. \end{steps} \end{proof} \subsection{Width reduction}\label{app:widthred} We use the branching procedure of Schuler~\cite{Sch05} in the form of~\cite[Section~3.2]{CIP06}. For $k\ge1$, the procedure $\textsc{Reduce}_k(F)$ works as follows on a CNF $F$ without tautological clauses. After every assignment it deletes satisfied clauses and removes false literals; no step creates a tautological clause. \begin{itemize} \item If $F$ contains the empty clause, stop; this leaf contributes nothing. If $F$ has no clause of width larger than $k$, output $F$ as a leaf. \item Otherwise let $C$ be the first clause of width larger than $k$, and let $C'\subset C$ consist of its first $k$ literals. Recurse on the \emph{left branch} $F_{\mathrm L}=(F\setminus\{C\})\cup\{C'\}$ and on the \emph{right branch} $F_{\mathrm R}$, which is $F$ with the $k$ literals of $C'$ set to false. \end{itemize} \begin{claim}\label[claim]{cl:partition} The satisfying assignments of $F$ are the disjoint union of those of $F_{\mathrm L}$ and of those of $F_{\mathrm R}$ extended by the assignment that falsifies $C'$. \end{claim} \begin{proof}[Proof of \cref{cl:partition}] \begin{steps} \step{1}{1} Every satisfying assignment $x$ of $F$ lies in exactly one of the two sets. \pf If $x$ satisfies $C'$, then $x$ satisfies $F_{\mathrm L}$, and $x$ does not falsify $C'$. If $x$ falsifies $C'$, then $x$ does not satisfy $F_{\mathrm L}$, and its restriction satisfies $F_{\mathrm R}$. \step{1}{2} Every element of the two sets satisfies $F$. \pf $F_{\mathrm L}$ implies $F$ because $C'\subseteq C$. An assignment that satisfies $F_{\mathrm R}$ and falsifies $C'$ satisfies every clause of $F$. \qedstep{1}{3} \pf By \sref{1}{1} and \sref{1}{2}. \end{steps} \end{proof} By induction, $\#F$ is the sum over the leaves of the number of satisfying assignments of the leaf formula over the variables that are still free at the leaf, and $F$ is satisfiable if and only if some leaf formula is. \begin{claim}\label[claim]{cl:leaves} Let $F$ have $n$ variables and $m$ clauses. Every leaf is reached along a path with at most $m$ left branches and $r\le\lfloor n/k\rfloor$ right branches, and its formula is a $k$-CNF on at most $n-kr$ variables. At most $\binom{m+r}{r}$ leaves have exactly $r$ right branches. \end{claim} \begin{proof}[Proof of \cref{cl:leaves}] \begin{steps} \step{1}{1} Every path has at most $m$ left branches. \pf A left branch replaces a clause of width larger than $k$ by one of width $k$. Right branches and simplifications never widen or create a clause. So the number of clauses of width larger than $k$ drops at every left branch and never grows. \step{1}{2} A path with $r$ right branches has $r\le n/k$, and its leaf has at most $n-kr$ free variables. \pf Each right branch fixes $k$ free variables. \step{1}{3} At most $\binom{m+r}{r}$ leaf paths have exactly $r$ right branches. \pf Pad each such path with trailing left branches to length $m+r$. No leaf path is a prefix of another, so two distinct paths with the same padding would be a prefix of one another. So the padding is injective into the words of length $m+r$ with $r$ right branches. \qedstep{1}{4} \pf By \sref{1}{1}--\sref{1}{3}; a leaf formula has no clause of width larger than $k$. \end{steps} \end{proof} \lemwidthred* \begin{proof}[Proof of \cref{lem:widthred}] \begin{steps} \step{1}{1} \Let $F$ have $n$ variables and $m\le n^c$ clauses, none of them tautological, and \Let $k=\lfloor K_0\log n\rfloor$. Run $\textsc{Reduce}_k(F)$, and solve each leaf as follows. A leaf with $n'\ge\sqrt n$ free variables is solved by the assumed algorithm, repeated $O(n)$ times with a majority vote, or the most frequent answer for counting. A leaf with $n'<\sqrt n$ free variables is solved by brute force. Combine the leaf answers by \cref{cl:partition}. \pf Deleting tautological clauses changes neither satisfiability nor the count. Small $n$ is handled by brute force. \step{1}{2} The assumed algorithm applies to every leaf with $n'\ge\sqrt n$, and each repeated run has error probability at most $2^{-2n}$. \pf Here $\log n'\ge\frac12\log n$, so the width is $k\le K_0\log n\le K'\log n'$. The number of clauses is at most $m\le n^c\le n'^{2c}$. Repetition with a majority vote reduces the error to $2^{-2n}$. \step{1}{3} The large leaves cost $O(n)\cdot\sum_{r}\binom{m+r}{r}O(2^{\rho(n-kr)})\le O(n)\cdot e\cdot2^{\rho n}$ in total. \pf By \cref{cl:leaves}, $\binom{m+r}{r}\le\binom{m+\lfloor n/k\rfloor}{r}$, and the binomial theorem gives \[ \sum_{r=0}^{\lfloor n/k\rfloor}\binom{m+r}{r}2^{\rho(n-kr)}\le2^{\rho n}\bigl(1+2^{-\rho k}\bigr)^{m+n/k} \le2^{\rho n}\exp\bigl((m+n/k)\,2^{-\rho k}\bigr)\le e\cdot2^{\rho n}. \] The last step uses $k\ge K_0\log n-1$, so $2^{-\rho k}\le2n^{-\rho K_0}=2n^{-2(c+1)}$, and $2(m+n/k)n^{-2(c+1)}\le2(n^c+n)n^{-2c-2}\le1$ for $n\ge2$. \step{1}{4} The tree has at most $2^{(\rho/2+o(1))n}$ leaves, and the small leaves cost $O(2^{\rho n})$ in total. \pf By \cref{cl:leaves}, the number of leaves is at most \[ \sum_{r\le n/k}\binom{m+r}{r}\le(n+1)\binom{m+\lfloor n/k\rfloor}{\lfloor n/k\rfloor}\le(n+1)\Bigl(\frac{e(m+n/k)}{n/k}\Bigr)^{n/k} \le(n+1)\,(2ekn^{c})^{n/k}. \] Its logarithm is at most $\frac{n}{K_0\log n-1}(c\log n+\log(2ek))+\log(n+1)=(c/K_0+o(1))\,n\le(\rho/2+o(1))\,n$, because $c/K_0=c\rho/(2(c+1))\le\rho/2$. Each small leaf costs $2^{\sqrt n}\poly(n)$. \step{1}{5} All leaf answers are correct with probability at least $1-2^{-n}$. \pf By \sref{1}{2}, \sref{1}{4} and a union bound over at most $2^n$ leaves. \qedstep{1}{6} \pf The tree has at most twice as many nodes as leaves, each with $\poly(n,m)$ work. With \sref{1}{3} and \sref{1}{4}, the total time is $O(2^{\rho n}\poly(n))$. By \sref{1}{5} and \cref{cl:partition}, the combined answer is correct with probability at least $1-2^{-n}\ge2/3$. \end{steps} \end{proof} \subsection{Hardness at logarithmic locality} \corlogsat* \begin{proof}[Proof of \cref{cor:logsat}] \begin{steps} \step{1}{1} Part (a) holds. \pf Let $c$ be the constant that \cref{hyp:cnfseth} gives for $\gamma/2$, and put $c'=2c$ and $\rho=1-\gamma$; let $K'$ be as in \cref{lem:widthred}. An $O(2^{(1-\gamma)n})$ algorithm for $k\le K'\log n$ and at most $n^{c'}$ clauses would, by \cref{lem:widthred}, solve CNF-SAT with at most $n^c$ clauses in time $O(2^{(1-\gamma)n}\poly(n))\subseteq O(2^{(1-\gamma/2)n})$, which contradicts \cref{hyp:cnfseth}. The counting statement follows in the same way from \cref{hyp:sharpcnfseth}. \step{1}{2} Part (b) holds. \pf Let $c,\rho_0$ be the constants of \cref{hyp:cnfeth}, and put $c'=2c$ and $\rho=\rho_0/2$. An $O(2^{\rho n})$ algorithm would solve CNF-SAT with at most $n^c$ clauses in time $O(2^{\rho n}\poly(n))\subseteq O(2^{\rho_0n})$. \qedstep{1}{3} \pf By \sref{1}{1} and \sref{1}{2}. \end{steps} \end{proof} \thmbarrier* \begin{proof}[Proof of \cref{thm:barrier}] \begin{steps} \step{1}{1} \Let $K',c'$ be given by \cref{cor:logsat}(a) for $\gamma/2$, and \Let $K=2K'+2$ and $c_\gamma=c'+2$. \Let $F$ be a $k$-CNF on $N$ variables with $k=\lfloor K'\log N\rfloor$ and at most $N^{c'}$ clauses, and \Let $S_F$ be the sample of \cref{lem:gadget}, in dimension $n=N+p$. \step{1}{2} The sample $S_F$ is a $\BP_{\lceil K\log n\rceil}$ sample of size at most $n^{c_\gamma}$, and $n\le N+K'\log N$. \pf The sparsity is at most $2k\le K\log n$, the size is at most $N^{c'}+k\le n^{c'}+n\le n^{c'+2}$, and $p\le k$. \step{1}{3} A consistency test in time $O(2^{(1-\gamma)n})$ contradicts \cref{cor:logsat}(a). \pf It decides $F$ in time $O(2^{(1-\gamma)(N+K'\log N)})+\poly(N)\subseteq O(2^{(1-\gamma/2)N})$. \step{1}{4} A proper $(n^{-c_\gamma},1/3)$-PAC learner in time $O(2^{(1-\gamma)n})$ contradicts \cref{cor:logsat}(a). \pf The argument of \cref{thm:equivalence}(iii) needs an accuracy below $1/(M+p)$, and $n^{-c_\gamma}\le1/(2(n^{c'}+n))\le1/(2(M+k))$. It gives a one-sided randomized algorithm for $F$ with the time bound of \sref{1}{3}. \step{1}{5} The counting and CNF-ETH statements hold. \pf Use \cref{thm:equivalence}(ii) with the counting part of \cref{cor:logsat}(a), and \cref{cor:logsat}(b), in the same way. \qedstep{1}{6} \pf By \sref{1}{3}--\sref{1}{5}. \end{steps} \end{proof} \corsparsity* \begin{proof}[Proof of \cref{cor:sparsity}] \begin{steps} \step{1}{1} Part (a) holds. \pf The class $\BP_k$ is $k$-local with $N=n$, and consistency is the question whether $|\VS(S)|>0$. Apply \cref{thm:realizable} with $\kappa=k$. \step{1}{2} Part (b) holds. \pf By \cref{thm:barrier}. A $\lceil K\log n\rceil$-sparse sample is also $k$-sparse for every integer $k\ge K\log n$, so the hardness extends to all such $k$. \step{1}{3} The statements hold for $\LD_k$. \pf Part (a) holds as in \sref{1}{1}. For (b), a $k$-CNF without tautological clauses is a sample of positive $\LD_k$ examples (\cref{ex:local}(a)), so \cref{cor:logsat} applies directly, and the argument of \cref{thm:equivalence}(iii) covers learners. \qedstep{1}{4} \pf By \sref{1}{1}--\sref{1}{3}. \end{steps} \end{proof} \subsection{Sample-sensitive realizable learning} \thmmoderate* \begin{proof}[Proof of \cref{thm:moderate}] \begin{steps} \step{1}{1} \Let $S$ be a sample of $m=\lceil\mVC\rceil$ examples. With probability at least $1-\delta$, every $w\in\VS(S)$ has $\err_\cD(w)\le\eps$. \pf \Cref{fact:samples}(b). \step{1}{2} With probability $1$, $\VS(S)\ne\emptyset$. \pf Because $\opt=0$, some $w^*$ has $\err_\cD(w^*)=0$, so each example is consistent with $w^*$ with probability $1$. \step{1}{3} If $\VS(S)\ne\emptyset$, the following procedure outputs an element of $\VS(S)$ after at most $\kappa m+1$ profile computations. Process the bits of $R(S)$ in order, and fix each to a value for which the coefficient of $V^0$ in the profile of the descriptions that extend the current partial assignment stays positive. Set all other bits to $0$. \pf The coefficient is positive at the start, and at each step it is the sum of the coefficients for the two values, so one value keeps it positive. At the end all bits of $R(S)$ are fixed, and a positive coefficient of $V^0$ means that the fixed bits make no error. The other bits do not affect any label. \step{1}{4} Each profile computation takes 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 The time is \cref{lem:profile}. For the bound on $\log s$: because $C_B\ge1$ and $\log(2/\eps)\ge1$, we have $s\ge4m\ge4d/\eps\ge2d/\eps\ge2$. \step{1}{5} The total time satisfies the displayed bound. \pf By \sref{1}{4}, $s/\sqrt{\log s}\le(6\kappa m+\kappa^2)/\sqrt{\log(2d/\eps)}$, and $m=O((d\log(2/\eps)+\log(2/\delta))/\eps)$. The factor $\kappa m+1$ of \sref{1}{3} is polynomial. \step{1}{6} For constant $\eps$ and $\delta$ the time is $2^{O(\kappa N/\sqrt{\log N}+\kappa^2)}$. \pf Here $m=O(d)$ and the exponent is $O(\kappa d/\sqrt{\log(2d/\eps)}+\kappa^2)$. The function $x\mapsto x/\sqrt{\log x}$ is increasing for $x\ge2$, and $d\le N$, so $d/\sqrt{\log(2d/\eps)}=O(N/\sqrt{\log N})$. \qedstep{1}{7} \pf By \sref{1}{1}--\sref{1}{6}. The exponent is $o(N)$ when $\kappa=o(\sqrt{\log N})$, because then also $\kappa^2=o(\log N)$. \end{steps} \end{proof}