\section{Roadmap of the appendix}\label{app:roadmap}

The appendix contains the full proofs of the results of the main text, in the order of the sections, and
ends with a table of notation. Three short results are proved where they are stated: \cref{lem:vscnf},
\cref{cor:kdep} and \cref{cor:sparsemaxsat}. \Cref{fig:dependency} shows how the results depend on each
other.

\Cref{app:engine} builds the engine. It writes a factor graph as a tensor network (\cref{lem:fg2tn}). The
contraction theorem of~\cite{OAI26} then gives the sparse sum-product theorem (\cref{thm:sumproduct}), and
this theorem gives the exact error profiles (\cref{lem:profile}). Later sections use these results for
sample-sensitive learning, ERM, the exponential mechanism and inference.

\Cref{app:locality} proves \cref{thm:A}. \Cref{app:transfer} proves the realizable transfer
(\cref{thm:realizable}). \Cref{app:gadget} builds the perceptron gadget (\cref{lem:gadget}) and proves that
proper learning is equivalent to bounded-width SAT (\cref{thm:equivalence}). \Cref{app:widthred} reduces
CNF-SAT to $k$-SAT with $k=O(\log n)$ (\cref{lem:widthred}). \Cref{app:loghard} uses this reduction to
prove the hardness at logarithmic locality (\cref{thm:barrier}) and the data-sparsity transition
(\cref{cor:sparsity}). \Cref{app:moderate} proves sample-sensitive realizable learning
(\cref{thm:moderate}), which moves the threshold to $\sqrt{\log N}$ at constant accuracy.

\Cref{app:accuracy} proves \cref{thm:B}. \Cref{app:erm} computes exact ERM from the error profile
(\cref{thm:erm}) and then treats consistency by length (\cref{cor:ermlen}), agnostic learning
(\cref{thm:agnostic}) and sparse Max-CSP (\cref{cor:maxcsp}). \Cref{app:expmech} proves exact private
learning with the exponential mechanism (\cref{thm:expmech}). \Cref{app:pcp} turns a short PCP into an
$\LD_3$ sample (\cref{lem:pcp2ld}). This gives the hardness at constant accuracy (\cref{thm:constacc}), the
two-way reduction between learning at constant accuracy and SAT by length (\cref{cor:satlen}) and Gap-3-SAT
under $\lenETH{C}$ (\cref{cor:gapsat}). \Cref{app:accbarrier} proves the hardness at inverse-polynomial
accuracy (\cref{thm:accbarrier}).

\Cref{app:treewidth} proves \cref{thm:C}. It starts with exact inference (\cref{thm:inference}) and its
separation from elimination and compilation (\cref{cor:separation}). OR-chains with copied variables
(\cref{lem:chain}) then give inference by length (\cref{cor:inflen}) and the lower bound under \#CNF-SETH
(\cref{thm:inflower}). The section ends with the treewidth transition (\cref{cor:twtransition}).

\Cref{app:ledger} contains the proofs for the ledger and the permutation obstacle. The branching procedure
of \cref{app:widthred} and the counting algorithm of~\cite{Cla26} show that sparse CNF-SAT is subexponential
(\cref{prop:sparsecnf}), and \cref{prop:dnf} gives the bound for proper $k$-term DNF learning under
CNF-SETH. The two-counter lemma (\cref{lem:counters}) gives the counts for Densest $k$-Subgraph, which
refute the hypothesis behind the single-ReLU bound (\cref{prop:dks}). \Cref{prop:relu} records what remains
of that bound, and \cref{prop:fas} shows that ERM for halfspaces on difference vectors is weighted Feedback
Arc Set.

\Cref{app:notation} lists the global symbols and where each one is defined.

\paragraph{How to read the proofs.}
We write the proofs in the structured style of Lamport~\cite{Lam95,Lam12}. A proof is a list of numbered
steps, and $\pflab{k}{j}$ is the $j$-th step at level $k$. Each step states a claim, and a proof of the
claim follows it. This proof is a short paragraph or a list of steps at the next level. The last step of
each list, \textsc{q.e.d.}, proves the goal of the list from the earlier steps. \textsc{Assume} and
\textsc{Prove} state the hypothesis and the goal of a step, \textsc{Let} introduces a symbol, and
\textsc{Case} marks one case of a case split. A reader who wants only the main idea can read the level-1
steps and skip their proofs. Each restated result keeps its number from the main text.

\begin{figure}[t]
\centering
\IfFileExists{figs/fig_dependency.pdf}{\includegraphics[width=\linewidth]{figs/fig_dependency.pdf}}{\fbox{dependency graph}}
\caption{Dependencies between the results. An arrow from $X$ to $Y$ means that the proof of $Y$ cites $X$,
after transitive reduction. Dashed frames mark imported theorems, thick frames mark the main theorems,
and hypotheses are not drawn. \Cref{thm:accbarrier}, \cref{prop:relu} and \cref{prop:fas} use no other
result of this paper.}
\label{fig:dependency}
\end{figure}
\newpage