\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}

\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}