\section{Proofs for Sections~\ref{sec:ledger} and~\ref{sec:outlook}}\label{app:ledger}

\propsparsecnf*

\begin{proof}[Proof of \cref{prop:sparsecnf}]
\begin{steps}
\step{1}{1} \Let $k\ge1$ be a constant with $\log(e(ck+1))/k\le\eps'/2$, and \Let $F$ be the formula
without its tautological clauses. Run $\textsc{Reduce}_k(F)$ of \cref{app:widthred}.
\pf The constant $k$ exists because $\log(e(ck+1))/k\to0$. Deleting tautological clauses changes neither
the count nor the number of variables.
\step{1}{2} The tree has at most $(n+1)(e(ck+1))^{n/k}\le(n+1)2^{\eps'n/2}$ leaves.
\pf By \cref{cl:leaves} with $m\le cn$ clauses, 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(e(mk/n+1)\bigr)^{n/k}$, and
$mk/n\le ck$.
\step{1}{3} Each leaf formula can be counted over its free variables in time $2^{o(n)}$.
\pf It is a $k$-CNF on at most $n$ variables. If at least $4$ variables occur in it and it has at least $2$
clauses, \cref{fact:claude} counts the occurring variables in time $2^{C_1k^2g(n)}=2^{o(n)}$, because $k$ is
constant. Otherwise brute force takes constant time. Each free variable that does not occur doubles the
count.
\qedstep{1}{4}
\pf By \cref{cl:partition}, the count of $F$ is the sum of the leaf counts. The tree has at most twice as
many nodes as leaves, with polynomial work per node. With \sref{1}{2} and \sref{1}{3}, the total time is
$(n+1)2^{\eps'n/2}\cdot2^{o(n)}\poly(n)=O(2^{\eps'n})$.
\end{steps}
\end{proof}

\begin{proposition}[Proper $k$-term DNF learning]\label[proposition]{prop:dnf}
Assume \cref{hyp:cnfseth}, and let $k\ge2$ be a constant. For every $\gamma>0$, no randomized algorithm
decides in time $O(2^{(1/2-\gamma)n})$ whether a sample of polynomial size in $\{0,1\}^n$ is consistent with
a $k$-term DNF. The same holds for proper PAC learning of $k$-term DNF to some inverse-polynomial
accuracy.
\end{proposition}

The proof encodes a CNF as a hypergraph on its literals and applies the reduction of Pitt and
Valiant~\cite{PV88}. The factor $1/2$ comes from encoding literals as separate elements. Whether proper
$k$-term DNF learning needs time $2^{(1-\gamma)n}$ under CNF-SETH, or admits a $2^{(1-\Omega(1))n}$
algorithm, is open.

\begin{proof}[Proof of \cref{prop:dnf}]
\begin{steps}
\step{1}{1} \Let $F$ be a CNF on $N$ variables. \Let $U=\{z_i,\bar z_i:i\le N\}\cup\{\bot\}\cup\{s_1,\dots,s_{k-2}\}$,
of size $2N+k-1$, and \Let $\mathcal E$ be the hypergraph on $U$ with the following edges: $\{z_i,\bar z_i\}$
for all $i$; $C\cup\{\bot\}$ for every clause $C$, where the literal $\neg z_i$ is the element $\bar z_i$;
$\{s_a,s_b\}$ for all $a\ne b$; and $\{s_a,u\}$ for all $a$ and all $u\notin\{s_1,\dots,s_{k-2}\}$. Then $F$ is
satisfiable if and only if $\mathcal E$ has a $k$-coloring in which no edge is monochromatic.
\begin{steps}
\step{2}{1} In such a coloring, the elements $s_a$ get $k-2$ distinct colors that no other element uses.
\pf By the edges $\{s_a,s_b\}$ and $\{s_a,u\}$.
\step{2}{2} If $\mathcal E$ has such a coloring $\chi$, then $F$ is satisfiable.
\pf By \sref{2}{1}, the other elements use two colors. Call them $0$ and $1$, with $\chi(\bot)=0$. The edge
$\{z_i,\bar z_i\}$ gives $z_i$ and $\bar z_i$ opposite colors, so under the assignment $z_i=\chi(z_i)$ the
color of each literal is its truth value. The edge $C\cup\{\bot\}$ is not monochromatic, so $C$ contains a
literal of color $1$, which is true.
\step{2}{3} If $F$ is satisfiable, then $\mathcal E$ has such a coloring.
\pf Color each literal by its truth value under a satisfying assignment, $\bot$ by $0$, and $s_a$ by $a+1$.
Each edge $C\cup\{\bot\}$ contains a true literal of color $1$ and $\bot$ of color $0$. The other edges are
bichromatic by construction.
\qedstep{2}{4}
\pf By \sref{2}{2} and \sref{2}{3}.
\end{steps}

\step{1}{2} \Let $U$ be identified with $[n]$, $n=2N+k-1$. \Let the sample consist of the positive
examples $p_u=\mathbf 1-e_u$ for all $u$ and the negative examples $q_Y=\mathbf 1-\ind_Y$ for all edges $Y$
of $\mathcal E$. Then $\mathcal E$ has a $k$-coloring without monochromatic edges if and only if some
$k$-term DNF is consistent with the sample~\cite{PV88}.
\begin{steps}
\step{2}{1} If $\chi$ is such a coloring, then $T_1\vee\dots\vee T_k$ with $T_a=\bigwedge_{u:\chi(u)\ne a}x_u$
is consistent.
\pf The term $T_{\chi(u)}$ does not contain $x_u$, so $T_{\chi(u)}(p_u)=1$. For every $a$, an edge $Y$
contains some $u$ with $\chi(u)\ne a$, so $x_u$ is in $T_a$ and $T_a(q_Y)=0$.
\step{2}{2} If $T_1\vee\dots\vee T_k$ is consistent, then coloring each $u$ by some $a$ with $T_a(p_u)=1$
leaves no edge monochromatic.
\pf Suppose that an edge $Y$ is monochromatic with color $a$. Every edge has at least two elements, so
$T_a$ accepts $p_u$ and $p_{u'}$ for two distinct $u,u'\in Y$. A negative literal $\neg x_v$ is true on
$p_u$ only if $v=u$, so $T_a$ has no negative literal. A literal $x_v$ with $v\in Y$ is false on $p_v$,
which $T_a$ accepts, so $T_a$ contains no such literal. Thus $T_a(q_Y)=1$, which contradicts consistency.
\qedstep{2}{3}
\pf By \sref{2}{1} and \sref{2}{2}.
\end{steps}

\qedstep{1}{3}
\pf The sample has polynomial size. An algorithm in time $O(2^{(1/2-\gamma)n})$ would decide $F$ in time
$O(2^{(1/2-\gamma)(2N+k-1)})=O(2^{(1-2\gamma)N})$, which contradicts \cref{hyp:cnfseth} with slack $2\gamma$.
For learners, use the argument of \cref{thm:equivalence}(iii) with the uniform distribution on the
sample.
\end{steps}
\end{proof}

\lemcounters*

\begin{proof}[Proof of \cref{lem:counters}]
\begin{steps}
\step{1}{1} \Let $P=n+D+1$. For $u\in\{0,\dots,D\}$, \Let $\Phi_u$ be the factor graph over $\Ring_{P,\ell}$ obtained
from $\Phi$ by replacing each monomial $V^eU^r$ with $u^r\bmod2^P$ times $V^e$, where $0^0=1$. Then
$Z(\Phi_u)=\sum_{i<\ell}g_i(u)V^i$ modulo $2^P$, where $g_i(u)=\sum_{j\le D}c_{i,j}u^j$.
\pf An assignment with an entry $0$ contributes $0$. Any other assignment $x$ contributes
$V^{A(x)}u^{B(x)}$, and $A(x)<\ell$, so nothing is truncated. Since $B(x)\le D$, the index $j$ stops at $D$.
\step{1}{2} All $Z(\Phi_u)$ can be computed in time $\poly(s+|\Phi|)\cdot2^{O(s/\sqrt{\log s})}$.
\pf $\Phi_u$ has the arity and the size of $\Phi$, and $P,\ell\le s$. An entry takes polynomial time: the exponents have
polynomially many bits, $u^r$ is computed modulo $2^P$ by repeated squaring, and $V^e=0$ in $\Ring_{P,\ell}$ for
$e\ge\ell$. \Cref{thm:sumproduct} applies to each of the $D+1\le s$ factor graphs.
\step{1}{3} Fix $i$. There are integers $b_0,\dots,b_D$ with $g_i(u)=\sum_{t\le D}b_t\,u^{\underline t}$ for all $u$,
where $u^{\underline t}=u(u-1)\cdots(u-t+1)$, and each $c_{i,j}$ is an integer combination of the $b_t$ with
coefficients computable in polynomial time. Moreover, the forward difference
$\Delta_t=\sum_{h=0}^t(-1)^{t-h}\binom th g_i(h)$ equals $t!\,b_t$.
\pf The polynomials $u^{\underline t}$ are monic with integer coefficients, so the matrix that expresses them in
monomials is unitriangular and has an integer inverse; this gives the $b_t$ from the $c_{i,j}$, and the $c_{i,j}$ from
the $b_t$. The forward difference operator satisfies $\Delta u^{\underline t}=t\,u^{\underline{t-1}}$, so its $t$-th power
at $0$ maps $u^{\underline{t'}}$ to $t!$ if $t'=t$ and to $0$ otherwise.
\step{1}{4} From $g_i(0),\dots,g_i(D)$ modulo $2^P$, each $b_t$ can be computed modulo $2^{n+1}$.
\pf $\Delta_t$ is known modulo $2^P$. Write $t!=2^vo$ with $o$ odd. By Legendre's formula, $v=t-\sigma_2(t)$, where
$\sigma_2(t)\ge1$ is the number of ones in the binary expansion of $t$, so $v\le t-1\le D-1$ for $t\ge1$, and $v=0$ for
$t=0$. By \sref{1}{3}, $\Delta_t/2^v=ob_t$, so $b_t$ is determined modulo $2^{P-v}$, and $P-v\ge n+1$.
\qedstep{1}{5}
\pf By \sref{1}{3} and \sref{1}{4}, each $c_{i,j}$ is known modulo $2^{n+1}$. It counts assignments of $n$ variables,
so $0\le c_{i,j}\le2^n<2^{n+1}$, and it is determined exactly. The recovery takes time polynomial in $s$ for each of
the at most $\ell\le s$ values of $i$.
\end{steps}
\end{proof}

\propdks*

\begin{proof}[Proof of \cref{prop:dks}]
\begin{steps}
\step{1}{1} \Let $\Phi$ have one variable $x_v$ for each vertex $v$, a factor with scope $\{v\}$ and table
$x_v\mapsto U^{x_v}$ for each vertex, and a factor with scope $\{u,v\}$ and table $V^{x_ux_v}$ for each edge $uv$. Then
$A(x)$ is the number of edges inside $T=\{v:x_v=1\}$, $B(x)=|T|$, and $c_{j,k}$ is the number of $k$-vertex subsets
that induce exactly $j$ edges.
\pf The exponent of $V$ is $1$ exactly on the edges with both ends in $T$, and the exponent of $U$ is $1$ exactly on
the vertices of $T$.
\step{1}{2} The counts can be computed in the stated time.
\pf Here $n=N$, the arity is at most $2$, $\|\Phi\|=N+2M$, $A(x)\le M$ and $B(x)\le N$. So \cref{lem:counters} applies
with $\ell=M+1$, $D=N$ and $s=4(N+2M)$: this $s$ is at least $n+D+1=2N+1$ and at least $\ell$, and $s\ge4$
gives $2\le s^{9/10}$.
\step{1}{3} A densest $k$-vertex subset can be found in the same time.
\pf The counts give the largest $j^*$ with $c_{j^*,k}>0$. Treat the vertices one at a time. To fix $x_v=b$, replace
the table of the vertex factor of $v$ by its restriction to $b$, with the entry $0$ on $1-b$, and compute the counts
again; keep a value of $b$ for which $c_{j^*,k}$ stays positive. Such a value exists, because the count is the sum of
the counts for the two values. This takes $2N$ further applications of \cref{lem:counters}, with the same $s$.
\step{1}{4} On graphs of maximum degree $d$, the time is $\poly(N)\cdot2^{O((d+1)N/\sqrt{\log N})}$, which is
$2^{O(N/\sqrt{\log N})}$ for $d=O(1)$ and $2^{o(N)}$ for $d=o(\sqrt{\log N})$.
\pf $M\le dN/2$, so $s\le4(d+1)N$, and $s\ge N$ gives $\log s\ge\log N$; and $\poly(N+M)=2^{o(N/\sqrt{\log N})}$
because $M\le N^2$.
\qedstep{1}{5}
\pf Let $C\ge1$, $\delta>0$ and $d$ be arbitrary. By \sref{1}{2} and \sref{1}{4}, for constant $d$ the numbers $c_{j,k}$
determine in time $2^{O(N/\sqrt{\log N})}=O(2^{\delta N})$ the exact number of edges of a densest $k$-vertex
subgraph, and so which of the two cases of Hypothesis~1 of~\cite{GKMR21} holds. So no constants $\delta$ and $d$ have the
required property, for any $C$.
\end{steps}
\end{proof}

\proprelu*

\begin{proof}[Proof of \cref{prop:relu}]
\begin{steps}
\step{1}{1} Part~(a) holds.
\begin{steps}
\step{2}{1} \cite[Lemma~14 and Proposition~13]{GKMR21}: there are a constant $C_*$ and, for all constants $d$ and
$\lambda>0$, a polynomial-time reduction from the gap problem with $C=C_*$, on graphs with $N$ vertices and maximum
degree $d$ and with $k\ge\lambda N$, to training one ReLU on samples in the unit ball with labels in $[0,1]$, with a
threshold $\opt$ and an additive gap $\eps=\Theta_{d,\lambda}(1/\sqrt N)$: the first case has a weight vector in the
unit ball with error at most $\opt$, and in the second case every weight vector in the unit ball has error above
$\opt+\eps$.
\pf Let $\xi$ be the threshold of the gap problem. With $\gamma=1/(1000d)$ and $\zeta=1/(10^{10}d^2)$, the gap
of~\cite{GKMR21} is
\[
\eps=\frac{\gamma\zeta\xi}{8\sqrt{2k}\,M}-\frac{(1-\gamma)\zeta}{32N}-\frac{\gamma\zeta\xi}{128kM}.
\]
We may assume $k\ge2$ and $k/3\le\xi\le M$. Indeed, if $\xi>M$ the second case holds. Adding edges one at a time finds
in polynomial time a set of $k$ vertices that induces at least $\lfloor k/2\rfloor\ge k/3$ edges or all the edges, which
decides the case $\xi\le k/3$. Then $M\le dN/2$ and $\xi\ge k/3$ give the first term a lower bound
$\gamma\zeta\sqrt\lambda/(12\sqrt2\,d\sqrt N)$, and $\xi\le M$ gives it an upper bound $\gamma\zeta/(8\sqrt{2\lambda N})$.
The third term is at most half of the first, and the second is $O(1/N)$.
\step{2}{2} \Assume a training algorithm in time $2^{(1/\eps^2)/(\log(1/\eps))^{a+\theta}}\poly(n,m)$. Run it on the instance
of \sref{2}{1} with accuracy $\eps$, and compare the error of its output with $\opt+\eps$. This decides the gap
problem.
\qedstep{2}{3}
\pf With $\eps=\Theta_{d,\lambda}(1/\sqrt N)$, we have $1/\eps^2=O_{d,\lambda}(N)$ and $\log(1/\eps)\ge(\log N)/3$ for large
$N$, and $n,m$ are polynomial in $N$. So the time is at most $2^{O_{d,\lambda}(N/(\log N)^{a+\theta})}\poly(N)\le
2^{N/(\log N)^a}$ for large $N$, which contradicts the assumption.
\end{steps}

\step{1}{2} Part~(b) holds.
\begin{steps}
\step{2}{1} A 3-CNF $F$ without tautological clauses, on $n_0\ge1$ variables with $M_0<8n_0^3$ clauses, gives a Set Cover
instance: the universe $W$ consists of the variables and the clauses, the $Y=2n_0$ sets are indexed by the literals, and
the set of a literal contains its variable and the clauses that contain it. $F$ is satisfiable if and only if at most
$t=n_0$ sets cover $W$.
\pf To cover the $n_0$ variables, at most $n_0$ sets must contain one literal per variable. These literals form an
assignment, and they cover the clauses if and only if it satisfies them.

\step{2}{2} \Let $\beta=0.01/Y^2$, and \Let $S$ be the following multiset of samples in $\R^{Y+2}$, with coordinates $z_T$ for
the sets, $z_1$ and $z_*$: $(e_1+\sum_{T\ni\omega}e_T,\,0)$ for each $\omega\in W$; $(e_*+e_T,\,\beta)$ for each set
$T$; $(e_1,1)$; and $(e_*,\beta)$. \Let $E(z)=\sum_{(x,y)\in S}([\langle z,x\rangle]_+-y)^2$. If at most $t$ sets cover
$W$, then $E(z)\le\beta^2t$ for some $z$ with $\|z\|^2\le Y+2$. This is the reduction
of~\cite[Theorem~8]{GKMR21}.
\pf Take $z_T=-1$ on the sets of a cover, $z_T=0$ on the others, $z_1=1$ and $z_*=\beta$. Every sample of the first
kind has inner product at most $0$, and the samples of the last two kinds are fit exactly. A sample of the second
kind has error $\beta^2$ if $T$ is in the cover and $0$ otherwise. Finally, $\|z\|^2\le t+1+\beta^2\le Y+2$.

\step{2}{3} If $E(z)<\beta^2(t+1)$ for some $z\in\R^{Y+2}$, then at most $t$ sets cover $W$.
\pf Since $t+1\le Y+1\le2Y$, we have $\beta^2(t+1)\le2\cdot10^{-4}/Y^3\le2\cdot10^{-4}$. The sample $(e_1,1)$ then gives
$z_1>0.9$. The sample $(e_*,\beta)$ gives $[z_*]_+<\beta(1+\sqrt{2Y})\le0.2/Y$. Let $\mathcal F$ be the family of
sets $T$ with $z_T+z_*\le0$. Each of them has error $\beta^2$ on its sample $(e_*+e_T,\beta)$, so $|\mathcal F|\le t$.
If some $\omega\in W$ were in no set of $\mathcal F$, then $z_T>-z_*\ge-0.2/Y$ for all $T\ni\omega$, so
$z_1+\sum_{T\ni\omega}z_T>0.9-0.2=0.7$, and the sample of $\omega$ would have error above $0.49$.

\step{2}{4} \Let $\Lambda_1=\lceil\sqrt{Y+1}\,\rceil$, $\Lambda_2=\lceil\sqrt{Y+2}\,\rceil$ and $\Lambda=\Lambda_1\Lambda_2$. Dividing
every $x$ by $\Lambda_1$, every $y$ by $\Lambda$ and every $z$ by $\Lambda_2$ gives an instance with rational entries,
samples in the unit ball and labels in $[0,1]$. Its average squared error at the image of $z$ is $E(z)/(|S|\Lambda^2)$.
With $\eps=\beta^2/(2|S|\Lambda^2)$, training to additive error $\eps$ decides $F$.
\pf Every $x$ has squared norm at most $Y+1$. By \sref{2}{2}, if $F$ is satisfiable the optimum over the unit ball is at
most $\beta^2t/(|S|\Lambda^2)$, so the output has error below $\beta^2(t+1)/(|S|\Lambda^2)$. By \sref{2}{3}, if $F$ is
unsatisfiable no weight vector has error below that value. So compare the error of the output with it.

\step{2}{5} $1/\eps=O(n_0^9)$, and the instance has size polynomial in $n_0$.
\pf $|S|=|W|+Y+2=3n_0+M_0+2=O(n_0^3)$, $\Lambda^2\le16(Y+1)(Y+2)=O(n_0^2)$, and $1/\beta^2=O(n_0^4)$.

\qedstep{2}{6}
\pf Let $\alpha<1/9$, and choose $\gamma>0$ with $9\alpha<1-\gamma$. The instance has dimension $n=2n_0+2$ and $m=|S|$
samples, so a training algorithm in time $2^{(1/\eps)^\alpha}\poly(n,m)$ decides 3-SAT on $n_0$ variables in time
$2^{O(n_0^{9\alpha})}\poly(n_0)\le2^{n_0^{1-\gamma}}$ for large $n_0$, by \sref{2}{4} and \sref{2}{5}, which contradicts
Almost-ETH. The reduction is deterministic, so a deterministic training algorithm contradicts the deterministic form
of the hypothesis and a randomized one its randomized form.
\end{steps}
\qedstep{1}{3}
\end{steps}
\end{proof}

\propfas*

\begin{proof}[Proof of \cref{prop:fas}]
\begin{steps}
\step{1}{1} For every $w$, the misclassified arcs form a feedback arc set.
\pf The arc $(i,j)$ is classified correctly if and only if $w_i>w_j$. A cycle of correctly classified arcs
would give $w_{i_1}>w_{i_2}>\dots>w_{i_1}$.
\step{1}{2} For every feedback arc set $B$, some $w$ misclassifies only arcs of $B$.
\pf The graph $([n],A\setminus B)$ is acyclic. Let $\mathrm{pos}(i)$ be the position of $i$ in a topological
order of it, and put $w_i=n-\mathrm{pos}(i)$. Every arc of $A\setminus B$ goes forward in this order, so it is
classified correctly.
\qedstep{1}{3}
\pf By \sref{1}{1} and \sref{1}{2}, the minimum weighted error equals the minimum weight of a feedback arc
set.
\end{steps}
\end{proof}