\section{Proofs for Section~\ref{sec:prelim}: the engine}\label{app:engine}

\begin{lemma}[Factor graphs as tensor networks]\label[lemma]{lem:fg2tn}
Let $\Phi$ be a factor graph of arity at most $a$ whose scopes are all nonempty, and let $u$ be the
number of variables in no scope. There is a bipartite Boolean tensor network $G_\Phi$ with at most
$4\|\Phi\|$ edges, at most $4\|\Phi\|$ vertices and maximum degree at most $\max\{a,3\}$, such that
$Z(\Phi)=2^{u}\cdot\mathrm{contraction}(G_\Phi)$. Every entry of $G_\Phi$ is either an entry of some table
$\psi_f$ or an element of $\{0,1\}$. The network can be built in time polynomial in the size of $\Phi$.
\end{lemma}

\begin{proof}[Proof of \cref{lem:fg2tn}]
\begin{steps}
\step{1}{1} \Let $G'$ be the following tensor network. Each factor $f$ is a vertex with one edge
(a \emph{port}) for each variable of $I_f$ and with tensor $\psi_f$. Each variable $v$ of degree
$\deg(v)\ge1$ gets a \emph{gadget} attached to its $\deg(v)$ ports:
\begin{itemize}
\item if $\deg(v)=1$, one vertex with the unary tensor $(1,1)$;
\item if $\deg(v)=2$, one vertex with the binary equality tensor;
\item if $\deg(v)\ge3$, a tree with $\deg(v)-2$ vertices of degree $3$, each with the ternary equality
tensor, whose $\deg(v)$ leaf edges are the ports of $v$ and which has $\deg(v)-3$ internal edges.
\end{itemize}
Then, for every variable $v$ and every assignment of its ports, the sum over the internal edges of its
gadget of the product of the gadget tensors is $1$ if all ports of $v$ carry the same bit, and $0$
otherwise.
\pf For $\deg(v)\le2$ this is the definition of the tensor. For $\deg(v)\ge3$, a product of ternary
equality tensors is nonzero only if every gadget vertex sees one bit on all three of its edges. The tree
is connected, so then all its edges carry one bit. Conversely, the constant assignment gives the product
$1$. So the sum is $1$ if the ports agree and $0$ otherwise.

\step{1}{2} $Z(\Phi)=2^u\cdot\mathrm{contraction}(G')$.
\pf By \sref{1}{1}, an assignment of the ports contributes to the contraction only if, for every
variable, all ports of the variable carry the same bit, and then it contributes exactly once. These
assignments correspond bijectively to the assignments $x$ of the $n-u$ variables that lie in some
scope, and their product is $\prod_f\psi_f(x|_{I_f})$. Each variable in no scope contributes the factor
$2$ to $Z(\Phi)$.

\step{1}{3} Subdividing every edge of $G'$ by a new vertex with the binary equality tensor gives a
bipartite network $G_\Phi$ with the same contraction.
\pf A new vertex forces its two edges to carry the same bit, so the assignments with nonzero product
correspond bijectively to those of $G'$, with the same product. Old vertices form one side and new
vertices the other.

\step{1}{4} The network $G_\Phi$ has at most $4\|\Phi\|$ edges, at most $4\|\Phi\|$ vertices, and maximum
degree at most $\max\{a,3\}$.
\pf A variable $v$ has $\deg(v)$ ports and at most $\deg(v)$ internal edges, so $G'$ has at most
$2\|\Phi\|$ edges, and $G_\Phi$ has at most $4\|\Phi\|$. The network $G'$ has $|\cF|\le\|\Phi\|$ factor
vertices, because every scope is nonempty, and at most $\sum_v\deg(v)=\|\Phi\|$ gadget vertices. The
subdivision adds at most $2\|\Phi\|$ vertices. Factor vertices have degree $|I_f|\le a$, gadget vertices
have degree at most $3$, and subdivision vertices have degree $2$.

\qedstep{1}{5}
\pf By \sref{1}{2}, \sref{1}{3} and \sref{1}{4}. All entries are table entries or bits, and the
construction takes polynomial time.
\end{steps}
\end{proof}

\thmsumproduct*

\begin{proof}[Proof of \cref{thm:sumproduct}]
\begin{steps}
\step{1}{1} \Let $\cF_0$ be the factors with empty scope, and let $\Phi'$ be $\Phi$ without them. Then
$Z(\Phi)=\bigl(\prod_{f\in\cF_0}\psi_f\bigr)\cdot Z(\Phi')$.
\pf A factor with empty scope contributes the same constant to every term.

\step{1}{2} \Case $\|\Phi'\|=0$. Then $Z(\Phi')=2^n$, and the theorem holds.
\pf Without factors every assignment contributes $1$.

\step{1}{3} \Case $\|\Phi'\|\ge1$. Then the network $G_{\Phi'}$ of \cref{lem:fg2tn} satisfies the
hypotheses of \cref{fact:contract} with the given $s$.
\pf It has at most $4\|\Phi'\|\le s$ edges and vertices. Here $s\ge4$, so $\lceil s^{9/10}\rceil\ge4$, and the
degree bound $\max\{a,3\}\le\lceil s^{9/10}\rceil$ follows from $a\le s^{9/10}$. The ring is $\Ring_{P,\ell}$
with $P,\ell\le s$. Each entry is a table entry, computable in polynomial time, or a bit. The
description of $G_{\Phi'}$ has polynomial size.

\qedstep{1}{4}
\pf In the first case use \sref{1}{2}. In the second, \cref{fact:contract} computes the contraction
of $G_{\Phi'}$ in time $\poly(s+|\Phi|)\cdot2^{O(s/\sqrt{\log s})}$ and polynomial space, by \sref{1}{3}.
Multiply by $2^u$ (\cref{lem:fg2tn}) and by the constants of \sref{1}{1} in $\Ring_{P,\ell}$.
\end{steps}
\end{proof}

\lemprofile*

\begin{proof}[Proof of \cref{lem:profile}]
\begin{steps}
\step{1}{1} \Let $R(S)=\bigcup_iR(x_i)$ and $n_S=|R(S)|\le\kappa m$. For $u\in\{0,1\}^{R(S)}$, \Let $\mathrm{mis}(u)$ be
the number of examples that a description extending $u$ misclassifies. Then $\mathrm{mis}(u)$ is well defined,
and $E_S(V)=2^{N-n_S}\sum_uV^{\mathrm{mis}(u)}$.
\pf The label $h_w(x_i)$ depends only on $w|_{R(x_i)}$, and $R(x_i)\subseteq R(S)$. Each $u$ has $2^{N-n_S}$
extensions.

\step{1}{2} \Let $\Phi_S$ be the factor graph on the variables $R(S)$ over $\Ring_{P,\ell}$ with
$P=n_S+1$ and $\ell=m+1$ and with one factor for each example $i$: scope $R(x_i)$, and table $1$ at the
patterns $\alpha$ with $f_{x_i}(\alpha)=y_i$ and $V$ elsewhere. Then $Z(\Phi_S)$ determines the integer
polynomial $\sum_uV^{\mathrm{mis}(u)}$.
\pf Each $u$ contributes $V^{\mathrm{mis}(u)}$. Because $\mathrm{mis}(u)\le m<\ell$, no term is truncated. Each coefficient is at
most $2^{n_S}<2^P$, so its residue modulo $2^P$ determines it.

\step{1}{3} The factor graph $\Phi_S$ satisfies the hypotheses of \cref{thm:sumproduct} with
$s=\max\{4\kappa m,m+1,\kappa^2\}$.
\pf The size is $\|\Phi_S\|\le\kappa m$, so $4\|\Phi_S\|\le s$. Also $P\le\kappa m+1\le s$, $\ell=m+1\le s$, and
$s\ge2$. The arity is at most $\kappa\le s^{1/2}\le s^{9/10}$. The entries take polynomial time.

\step{1}{4} Fixing a set of description bits to given values preserves \sref{1}{1}--\sref{1}{3}.
\pf Fixed bits in $R(S)$ restrict scopes and tables, and factors whose scope becomes empty are
constants (\cref{thm:sumproduct}). Each fixed bit outside $R(S)$ halves the factor $2^{N-n_S}$. Sizes,
$P$ and $\ell$ do not grow.

\qedstep{1}{5}
\pf By \sref{1}{2}--\sref{1}{4}, \cref{thm:sumproduct} computes the restricted profile in time
$\poly(N,m)\cdot2^{O(s/\sqrt{\log s})}$. Multiply by the power of $2$ from \sref{1}{1}.
\end{steps}
\end{proof}