\section{The permutation obstacle and open problems}\label{sec:outlook}

\subsection{The permutation obstacle}\label{sec:permutation}

Everything above concerns classes with discrete descriptions. With real-valued parameters, a local
class on sparse data can encode a different kind of problem.

\begin{restatable}[ERM for halfspaces on difference vectors]{proposition}{propfas}\label[proposition]{prop:fas}
Let $G=([n],A)$ be a digraph with nonnegative arc weights $\mathrm{wt}$. Consider the sample
$S_G=\{(e_i-e_j,1):(i,j)\in A\}$, in which the example of the arc $(i,j)$ has weight $\mathrm{wt}(i,j)$, and
homogeneous halfspaces $h_w(x)=\ind[\langle w,x\rangle>0]$ with $w\in\R^n$. Then the minimum over $w$ of
the weighted error $\sum_{(i,j)\in A}\mathrm{wt}(i,j)\,\ind[h_w(e_i-e_j)=0]$ is the minimum weight of a
feedback arc set of $G$.
\end{restatable}

This is the classical connection between learning to order and Feedback Arc Set~\cite{CSS99}, in the
language of halfspaces. The correctly classified arcs satisfy $w_i>w_j$, so they form an acyclic set.
Conversely, a topological order of the arcs outside a feedback arc set gives a $w$ that classifies all of
them correctly (\cref{app:ledger}). With negative examples as well, ERM becomes a weak-order variant of
Feedback Arc Set, and the discussion below applies to it unchanged.

Feedback Arc Set has a $2^n\poly(n)$ dynamic program~\cite{BFK+12}. An algorithm in time $(2-\gamma)^n$ is a
long-standing open problem, while $(1+\eps)$-approximation is possible in time
$(2-\gamma_\eps)^n$~\cite{BFIS25}. The classical ETH-based lower bound for Feedback Arc Set came from linear
reductions from bounded-width problems, so it now has no basis. Yet no $2^{o(n)}$ algorithm follows from
the new algorithms. The ETH-based $2^{\Omega(k\log k)}$ lower bounds for permutation
problems~\cite{LMS18s,CFG+17} have lost their basis as well, and they now stand as a hypothesis of their
own. Bounds for Hamiltonicity derived from CNF-SAT survive~\cite{CKN18}, while sparse and undirected
instances of Hamiltonicity and the Traveling Salesperson Problem beat $2^n$~\cite{BHKK12,Bjo14}. For rank
aggregation, Kemeny's rule and Feedback Arc Set on tournaments take time
$2^{O(\sqrt{\mathrm{OPT}})}$~\cite{KaSc10}.

The natural Boolean encodings of Feedback Arc Set use either $\Theta(n\log n)$ bits or $\Theta(n^2)$ bits. The
first records the positions in an order, which gives locality $\Theta(\log n)$. The second records the
pairwise orders, with transitivity constraints. Hamiltonian Cycle and the Traveling Salesperson Problem
behave in the same way. In the language of this paper, real-valued parameters turn ERM on sparse data
into a \emph{permutation problem}, whose natural encodings have logarithmic locality. That is the open
window of the first transition, where neither the new algorithms nor CNF-SETH decide the complexity.

\subsection{Open problems}\label{sec:open}

\begin{problem}[The locality window]\label{prob:window}
Consistency for $\kappa$-local classes is subexponential for $\kappa\ll(\log N)^{1/4}$ and CNF-SETH-hard for
$\kappa\gg\log N$ (\cref{thm:realizable,thm:barrier}). By \cref{thm:equivalence}, closing this window is the
same as determining the complexity of $k$-SAT for $k=(\log n)^{\Theta(1)}$. Can \#$k$-SAT with $k=\sqrt{\log
n}$ be solved in time $2^{o(n)}$?
\end{problem}

\begin{problem}[Constant accuracy beyond $\sqrt{\log N}$]\label{prob:constacc}
At a constant accuracy $\eps\le\eps_0$ and locality $\kappa\le(\log N)^{1/2-\theta}$, the exponent of proper
learning is $O(N/(\log N)^\theta)$ (\cref{thm:moderate}), and under $\lenETH{C}$ it is at least
$N/(\log N)^{C+\beta+1}$ for $\LD_3$ (\cref{thm:constacc}). For $\kappa\ge\sqrt{\log N}$, is it still $N/\polylog
N$, or does it reach $(1-o(1))N$ at $\kappa=K\log N$? A $(1-o(1))N$ lower bound at constant accuracy needs
gap hardness on instances with $(1+o(1))N$ variables.
\end{problem}

\begin{problem}[The agnostic window]\label{prob:agnostic}
For constant $\kappa$, the exponent of proper agnostic learning is $O(N/\sqrt{\log N})$ at constant accuracy
(\cref{thm:agnostic}), at least $N/\polylog N$ there under $\lenETH{C}$ (\cref{thm:constacc}), and
$(1-o(1))N$ at accuracy $N^{-3}/8$ under the Max-3-SAT Hypothesis (\cref{thm:accbarrier}). How does it grow
for $\eps=N^{-c}$ with $0<c<3$?
\end{problem}

\begin{problem}[The treewidth window]\label{prob:treewidth}
Determine the complexity of exact inference for bounded-degree models with $\tw\sqrt{\log\tw}\le n\le\tw^{O(1)}$
(\cref{cor:twtransition}). By \cref{sec:inflower}, this is the complexity of \#SAT on formulas with $N$
variables and length between $N\sqrt{\log N}$ and $N^{O(1)}$.
\end{problem}

\begin{problem}[Permutations]\label{prob:fas}
Can Feedback Arc Set, that is, ERM for real-valued homogeneous halfspaces on positive examples of the form
$e_i-e_j$, be solved in time $2^{o(n)}$? Even time $(2-\gamma)^n$ is open~\cite{BFIS25}. Does a hypothesis
about permutation problems, such as the one of~\cite{LMS18s}, follow from a hypothesis about SAT?
\end{problem}

\begin{problem}[Improper learning]\label{prob:improper}
The new algorithms evaluate signed sums of tensor networks and low-degree interpolants. Do such
representations, used as \emph{hypothesis classes}, give new improper learners for dense classes, as
polynomial threshold functions did for DNF~\cite{KS04}?
\end{problem}

\subsection{Conclusion}\label{sec:conclusion}

The refutation of ETH is a statement about sparse, bounded-width structure, and learning inherits it
through locality. Accuracy decides which form of SAT governs learning: consistency is SAT by the number of
variables, and constant-accuracy learning is SAT by the length of the formula. Where examples are dense,
where agnostic learning must reach inverse-polynomial accuracy, and where a model may be polynomially
larger than its treewidth, the surviving hypotheses keep the old exponents. The boundary lies at
logarithmic locality, between fixed-width and unbounded-width SAT, and the permutation problems of
learning to order lie inside it.