\section{Notation}\label{app:notation}

The table lists the global symbols. Three of them have two closely related meanings, which the context
always fixes: $n$, $k$ and $c$. Symbols that occur only inside one proof are defined there.

\begin{center}\small
\begin{tabular}{@{}L{2.9cm}L{9.6cm}L{2.4cm}@{}}
\toprule
Symbol & Meaning & Defined in\\
\midrule
$N$ & description length: number of description bits & \cref{def:local}\\
$n$ & number of variables of a CNF or factor graph; dimension of the data & \cref{sec:model}\\
$m$, $M$ & sample size; number of clauses or constraints & \cref{sec:model}\\
$k$, $\kappa$ & clause width or data sparsity; locality & \cref{def:local}\\
$R(x)$, $f_x$, $R(S)$ & bits read by example $x$; its predicate; $\bigcup_iR(x_i)$ & \cref{def:local}\\
$w$, $\sigma$, $h_w$ & description; sign vector; hypothesis & \cref{sec:local}\\
$S$, $\VS(S)$ & sample; version space & \cref{sec:model}\\
$\err_S$, $\err_\cD$, $\opt$ & empirical error; true error; best true error & \cref{sec:model}\\
$E_S(V)$, $c_j$, $\mathrm{mis}(u)$ & error profile; number of descriptions with $j$ errors; errors of a restriction $u$ & \cref{sec:model}\\
$d$ & VC dimension & \cref{fact:samples}\\
$\eps$, $\delta$ & accuracy; confidence & \cref{sec:model}\\
$\epsdp$, $\eta$ & privacy parameter; statistical distance & \cref{thm:expmech}\\
$\mOcc$, $\mVC$, $\mUC$ & sample sizes; constants $C_0,C_B$ & \cref{fact:samples}\\
$C_1$ & constant of \cref{fact:claude} & \cref{fact:claude}\\
$g$, $T_\kappa(N)$ & rate function; time bound of the realizable transfer & \cref{sec:locality}\\
$\Gamma_S$ & CNF whose solutions are the version space & \cref{lem:vscnf}\\
$\Ring_{P,\ell}$, $V$ & ring $(\Z/2^P\Z)[V]/(V^\ell)$; its variable & \cref{sec:imported}\\
$\Phi$, $\cF$, $I_f$, $\psi_f$ & factor graph; factors; scope; table & \cref{sec:engine}\\
$Z(\Phi)$, $\|\Phi\|$, $|\Phi|$, $a$ & partition function; size; bit length; arity & \cref{sec:engine}\\
$G$, $\partial v$, $\psi_v$ & tensor network; edges at $v$; tensor at $v$ & \cref{sec:imported}\\
$s$ & size parameter of the engine & \cref{thm:sumproduct}\\
$\rho$ & rate of an algorithm or hypothesis of the form $2^{\rho n}$ & \cref{lem:widthred}\\
$\gamma$, $\theta$ & slack of a hypothesis, as in $2^{(1-\gamma)n}$; slack of an exponent & \cref{sec:hyp}\\
$\mu$, $\nu$ & exponents of $k$ and of $\log n$ in a $k$-SAT algorithm & \cref{cor:kdep}\\
$c$ & clause exponent ($n^c$ clauses) or clause density ($cn$ clauses), as stated & \cref{hyp:cnfseth}\\
$K_0$, $K'$, $K$ & branching width and hypothesis width of the width reduction; sparsity constant of the barrier & \cref{lem:widthred,thm:barrier}\\
$L$, $C$ & length of a CNF; rate of $\lenETH{C}$ & \cref{hyp:leneth}\\
$q$, $\beta$, $c_V$, $c_q$ & PCP queries; polylog exponent; size constant; $c_q=2q2^qc_V$ & \cref{fact:pcp}\\
$\Omega_F$, $\tau$, $Q_\tau$, $D_\tau$ & seeds; a seed; its query set; its predicate & \cref{fact:pcp}\\
$\eps_0$ & accuracy of the PCP reduction, $1/(q2^{q+2})$ & \cref{lem:pcp2ld}\\
$\tw$, $t$ & treewidth; width of a given path decomposition & \cref{sec:treewidth}\\
$\LD_k$, $\BP_k$ & literal disjunctions; binarized perceptrons & \cref{ex:local}\\
\bottomrule
\end{tabular}
\end{center}