\documentclass[11pt]{article}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage[hidelinks]{hyperref}
\usepackage{fancyhdr}
\usepackage{needspace}

\hypersetup{
  pdftitle={Some exposition of "The Exponential Time Hypothesis Is False"},
  pdfauthor={},
  pdfsubject={Subexponential exact counting of independent sets in cubic graphs},
  pdfkeywords={independent sets, counting, ETH, polynomial interpolation, SWAP operators}
}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\small Subexponential counting of independent sets}
\fancyhead[R]{\small\thepage}
\renewcommand{\headrulewidth}{0.3pt}
\setlength{\headheight}{14pt}
\setlength{\emergencystretch}{2em}
\setlength{\parskip}{3pt}
\setlength{\parindent}{1.2em}
\raggedbottom
\allowdisplaybreaks[1]
\setlist[enumerate]{leftmargin=*,itemsep=3pt,topsep=4pt}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}

\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newcommand{\Z}{\mathbb Z}
\newcommand{\E}{\mathbb E}
\newcommand{\one}{\mathbf 1}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\IS}{\operatorname{IS}}
\newcommand{\VC}{\operatorname{VC}}
\newcommand{\ket}[1]{\lvert #1\rangle}
\newcommand{\norm}[1]{\lVert #1\rVert}

\title{Some exposition of\\[3pt]
``The Exponential Time Hypothesis Is False''\thanks{Produced by \texttt{odonnell@cs.cmu.edu} through interaction with LLMs.}}
\author{}
\date{October 26, 2026}

% A compact title block without an author line or an empty author placeholder.
\makeatletter
\def\@maketitle{%
  \newpage\null\vskip 0.5em
  \begin{center}
    {\LARGE\@title\par}
    \vskip 1.2em
    {\large\@date\par}
  \end{center}
  \par\vskip 1em
}
\makeatother

\begin{document}
\maketitle
\thispagestyle{plain}
\vspace{-1.0em}

\section{The plan}

The goal is to count the independent sets of a $v$-vertex $3$-regular graph in time roughly
\[
  2^{O(v/\sqrt{\log v})}.
\]
The argument below is a specialization of Sections~2--4 of the manuscript
\emph{The Exponential Time Hypothesis Is False}~\cite{OAI26}.
We will deliberately use loose, easily checked parameters rather than optimize logarithmic factors.
They give the following clean, weaker bound.

\begin{theorem}\label{thm:main}
The number of independent sets of a $v$-vertex $3$-regular graph can be computed exactly by a Las Vegas randomized algorithm in expected time
\begin{equation}\label{eq:main-time}
  v^{O(1)}2^{O\left(v/(\log v)^{1/4}\right)}=2^{o(v)},
\end{equation}
using polynomial space.
\end{theorem}

This already suffices for the intended complexity consequence. Liu and Chen~\cite[Theorem~11]{LC24} prove that, assuming $\#\mathrm{ETH}$, counting vertex covers in $v$-vertex $3$-regular graphs requires exponential time. The complementation bijection
\[
  S\text{ is independent}\quad\Longleftrightarrow\quad
  V\setminus S\text{ is a vertex cover}
\]
transfers their lower bound to independent sets. As $\mathrm{ETH}$ implies $\#\mathrm{ETH}$, a \emph{deterministic} $2^{o(v)}$ exact counter would refute ETH.

We describe a randomized algorithm only to simplify one combinatorial labeling step. It always outputs the correct count; randomness affects only how quickly a suitable labeling is found. This step can be derandomized by the method of conditional expectations, without changing the time bound. We omit the derandomization, which is given in the more general setting of~\cite[Section~4.4]{OAI26}.

The key algebraic step is a familiar distributional approximation of parity, applied to commuting SWAP operators. The resulting low-rank correction is represented by a small number of \emph{exact} linear measurements. Finally, formal Taylor expansion, Boolean M\"obius inversion, and Hermite interpolation reconstruct the count. The latter tools are classical; we give the elementary calculation rather than treating it as a new interpolation principle.

All logarithms are base two. The number of graph vertices is $v$. For the auxiliary matrix we use
\[
  \begin{aligned}
  d&=\text{local register dimension},\qquad
  n=\text{number of register pairs},\\
  N&=d^{2n}=\text{matrix dimension}.
  \end{aligned}
\]
The integer $b$ will bound the degree of a polynomial and the number of exceptional SWAP locations. The quantum notation is simply convenient language for real symmetric matrices; the algorithm is classical.

\section{A classical approximation of parity}

Our only approximation ingredient is an old idea: interpolate a symmetric Boolean function on the Hamming-weight layers carrying almost all the probability mass. The historical chain deserves some care. Bhatnagar, Gopalan, and Lipton~\cite{BGL06} gave the finite-characteristic symmetric-polynomial ingredient. A proof communicated by Wigderson appears in Viola's exposition~\cite[Section~1.2.3]{Vio09}. Srinivasan~\cite[Lemma~14]{Sri13} formulated the product-distribution extension over arbitrary fields, and Alman and Williams~\cite[Lemma~3.1]{AW15} gave a particularly useful integral interpolation formulation. We use only the following elementary rational-polynomial specialization.

\begin{lemma}[Typical-weight interpolation]\label{lem:parity}
Let $p\in[1/4,1/2]$, and suppose $32\le b\le n/6$. There is an explicitly constructible rational polynomial $f$ of degree at most $b$ such that, for $J\sim\Bin(n,p)$,
\begin{equation}\label{eq:parity-error}
  \Pr[f(J)\ne(-1)^J]\le \rho,
  \qquad \rho:=2\exp\!\left(-\frac{b^2}{8n}\right).
\end{equation}
\end{lemma}

\begin{proof}
Choose $b+1$ consecutive integers
$\{a,a+1,\ldots,a+b\}\subseteq\{0,\ldots,n\}$
centered as closely as possible around $np$. Set
\begin{equation}\label{eq:parity-polynomial}
  f(z)=(-1)^a\sum_{j=0}^{b}(-2)^j\binom{z-a}{j}.
\end{equation}
For $0\le k\le b$, the binomial theorem gives
\[
  f(a+k)=(-1)^a\sum_{j=0}^{k}(-2)^j\binom{k}{j}=(-1)^{a+k}.
\]
The interval contains every integer within $b/4$ of $np$ (using $b\ge32$ and $p\in[1/4,1/2]$). Hoeffding's inequality gives
\[
  \Pr[|J-np|>b/4]\le2\exp(-b^2/(8n)),
\]
which proves the claim.
\end{proof}

The polynomial is deterministic. The probability in the lemma measures its set of \emph{disagreement weights}, not a random choice of polynomial. In the construction below those exceptional weights will be retained, not ignored.

\section{The approximation lemma in matrix form}

Fix $d\ge2$ and consider the tensor-product space
\begin{equation}\label{eq:hilbert}
  \mathcal H=(\C^d\otimes\C^d)^{\otimes n},
  \qquad \dim\mathcal H=N=d^{2n}.
\end{equation}
For $t\in[n]$, let $S_t$ exchange the two registers in the $t$th pair. The operators $S_t$ are real symmetric, commute, and satisfy $S_t^2=I$. Define
\begin{equation}\label{eq:operators}
  A_t=\frac{I-S_t}{2},\qquad
  W=\sum_{t=1}^{n}A_t,\qquad
  U=\prod_{t=1}^{n}S_t.
\end{equation}
Here $A_t$ is the orthogonal projector onto the antisymmetric subspace of pair $t$; $U$ swaps every pair.

Apply Lemma~\ref{lem:parity} with $p=(d-1)/(2d)$.
Define
\begin{equation}\label{eq:M}
  M=Uf(W).
\end{equation}
If $f(z)=\sum_j f_jz^j$, the notation $f(W)$ means simply $\sum_j f_jW^j$. The matrix $M$ is rational and real symmetric. In quantum language it is an observable, though it need not be a unitary or a contraction.

Index the computational basis by
\[
  \Omega=[d]^n\times[d]^n.
\]
For a row label write $\omega=(\alpha,\beta)$; for a column label write $\eta=(\alpha',\beta')$. The $t$th pair of the corresponding basis vector is $\ket{\alpha_t\beta_t}$.

\begin{lemma}[The matrix construction]\label{lem:matrix}
The matrix $M$ in~\eqref{eq:M} has the following properties.
\begin{enumerate}[label=\textup{(\roman*)}]
  \item Its error has small rank:
  \begin{equation}\label{eq:rank}
    \rank(I-M)\le\rho N.
  \end{equation}
  \item Its support is nearly a complete swap:
  \begin{equation}\label{eq:support}
    M_{\omega,\eta}\ne0
    \quad\Longrightarrow\quad
    \bigl|\{t\in[n]:\alpha'_t\ne\beta_t\}\bigr|\le b.
  \end{equation}
  \item There is an explicit matrix $C\in\{0,1,-1\}^{s_0\times N}$ with $s_0\le\rho N$ such that
  \begin{equation}\label{eq:measurements-determine}
    Cz=Cz'\quad\Longrightarrow\quad
    (I-M)z=(I-M)z'
    \qquad(z,z'\in\Q^N).
  \end{equation}
\end{enumerate}
The data can be constructed in time polynomial in $N$ and $n$.
\end{lemma}

\begin{proof}
\emph{Spectral agreement and rank.}
The symmetric and antisymmetric subspaces of a single register pair have dimensions
\[
  d_+=\frac{d(d+1)}2,
  \qquad
  d_-=\frac{d(d-1)}2.
\]
Choose a tensor-product eigenbasis for the $S_t$. A basis vector having exactly $j$ antisymmetric pairs satisfies
\[
  W\psi=j\psi,\qquad
  U\psi=(-1)^j\psi,\qquad
  M\psi=(-1)^jf(j)\psi.
\]
The total dimension of this eigenspace is
$\binom njd_-^jd_+^{n-j}$. Consequently,
\begin{align}
  \frac{\rank(I-M)}N
  &=\sum_{j:\,f(j)\ne(-1)^j}
     \binom nj\left(\frac{d_-}{d^2}\right)^j
               \left(\frac{d_+}{d^2}\right)^{n-j}\notag\\
  &=\Pr_{J\sim\Bin(n,p)}[f(J)\ne(-1)^J]
  \le\rho.\label{eq:rank-probability}
\end{align}
Thus the distributional disagreement probability is exactly the relative rank of the matrix error.

\medskip\noindent\emph{Degree and support.}
Because $W$ is an affine linear combination of the commuting involutions $S_t$ and $\deg f\le b$, expansion and the relations $S_t^2=I$ give
\[
  f(W)=\sum_{\substack{T\subseteq[n]\\|T|\le b}}
       \gamma_T\prod_{t\in T}S_t
\]
for rational coefficients $\gamma_T$. Hence
\begin{equation}\label{eq:near-swaps}
  M=\sum_{\substack{T\subseteq[n]\\|T|\le b}}
       \gamma_T\prod_{t\notin T}S_t.
\end{equation}
Every permutation in this sum swaps all pairs outside a set of size at most $b$. A nonzero $(\omega,\eta)$ entry in such a permutation requires $\alpha'_t=\beta_t$ outside that set. If more than $b$ coordinates disagree, every summand has zero entry there. This proves~\eqref{eq:support}.

\medskip\noindent\emph{Small-integer measurements.}
For one pair, use the unnormalized orthogonal eigenbasis
\begin{equation}\label{eq:local-basis}
  \ket{aa}\quad(a\in[d]),\qquad
  \ket{ab}+\ket{ba},\quad
  \ket{ab}-\ket{ba}\quad(a<b).
\end{equation}
The first two kinds are symmetric and the last is antisymmetric. Tensoring these vectors gives an orthogonal basis of $\Q^N$, all of whose entries lie in $\{0,1,-1\}$.

Let the rows of $C$ be the transposes of those basis vectors on which $M$ does not act as the identity. Equation~\eqref{eq:rank-probability} shows that there are at most $\rho N$ such vectors. If $C(z-z')=0$, then $z-z'$ is orthogonal to every exceptional basis vector. It is therefore a linear combination of vectors fixed by $M$, proving~\eqref{eq:measurements-determine}.

Enumerating this basis, constructing the polynomial in~\eqref{eq:parity-polynomial}, and evaluating it on the $N\times N$ matrix $W$ all take polynomial time in $N$ and $n$.
\end{proof}

The rank bound alone would not suffice for the algorithm: a rational linear measurement with unrestricted coefficients can distinguish all Boolean vectors. The useful extra conclusion is the explicit $\{0,1,-1\}$ measurement matrix. On Boolean inputs, each of its rows takes one of at most $2N+1$ integer values.

Lemma~\ref{lem:matrix} is the combination of Lemmas~4.1--4.2 of~\cite{OAI26}. The exceptional directions are not thrown away. They will be retained through $Cz$, so all subsequent calculations remain exact.

\section{Low-degree replacement forms}

At point $t\in[n]$, interpret the first label $\alpha_t$ of $z_{\alpha,\beta}$ as its group, and the second label $\beta_t$ as the group in which we would like to evaluate its replacement. The groups of auxiliary coordinates are
\[
  \Omega_{t,g}=\{(\alpha,\beta)\in\Omega:\alpha_t=g\}
  \qquad(g\in[d]).
\]

For a nonzero entry $M_{\omega,\eta}$, define its bad locations and the corresponding root polynomial by
\begin{equation}\label{eq:root-polynomial}
  B_{\omega,\eta}=\{t:\alpha'_t\ne\beta_t\},
  \qquad
  \phi_{\omega,\eta}(T)
    =\prod_{t\in B_{\omega,\eta}}\left(1-\frac{T}{t}\right).
\end{equation}
The support condition gives $\deg\phi_{\omega,\eta}\le b$. Now put
\begin{equation}\label{eq:K}
  K_\omega(T,z)
    =((I-M)z)_\omega
     +\sum_{\eta:\,M_{\omega,\eta}\ne0}
       M_{\omega,\eta}\phi_{\omega,\eta}(T)z_\eta.
\end{equation}
This is linear in $z$, with polynomial coefficients in $T$.

\begin{lemma}\label{lem:replacement}
For every $\omega=(\alpha,\beta)\in\Omega$, the form $K_\omega$ satisfies
\[
  K_\omega(0,z)=z_\omega,
  \qquad
  \deg_TK_\omega\le b.
\]
At every $t\in[n]$, its value $K_\omega(t,z)$ is determined by the shared measurements $Cz$ and the coordinates $z|_{\Omega_{t,\beta_t}}$ in the desired group.
\end{lemma}

\begin{proof}
At zero every root polynomial equals one, so the two terms in~\eqref{eq:K} sum to $z_\omega$. The degree bound is immediate. At $T=t$, every term whose column is outside $\Omega_{t,\beta_t}$ vanishes because its root polynomial contains $1-T/t$. The remaining part of the sum is local to that group, and $((I-M)z)_\omega$ is determined by $Cz$ by Lemma~\ref{lem:matrix}.
\end{proof}

This is the passage from the matrix construction to the polynomial replacements in~\cite[Section~4.3]{OAI26}. It explains why both parts of the matrix lemma are needed: low-rank error gives few shared measurements, while near-swap support gives low-degree root polynomials.

\section{Putting the graph into the auxiliary arrays}

Let $G=(V,E)$ be $3$-regular, with $|V|=v$ and $|E|=3v/2$. For each edge $e$, label its two endpoint occurrences by $1,2$ and write $u(e,i)$ for the corresponding vertex. Thus the incidence set
\[
  \mathcal I=E\times\{1,2\}
\]
has size $3v$. We work with simple graphs; no further generality is needed.

For a Boolean vector $x\in\{0,1\}^V$, let $x_u=1$ mean that $u$ is selected. The count is
\begin{equation}\label{eq:IS-formula}
  Z(G)=\#\IS(G)
    =\sum_{x\in\{0,1\}^V}
       \prod_{e\in E}\bigl(1-x_{u(e,1)}x_{u(e,2)}\bigr).
\end{equation}
Each factor indicates that the two endpoints of its edge are not both selected.

\subsection{Random group labels}

Independently choose uniform labels
\[
  \alpha_u\in[d]^n\quad(u\in V),
  \qquad
  \beta_e\in[d]^n\quad(e\in E).
\]
At point $t$, vertex $u$ belongs to group $\alpha_u(t)$ and the entire edge factor for $e$ is assigned to group $\beta_e(t)$. The assigned group need not contain either endpoint. Give incidence $(e,i)$ the auxiliary label
\[
  \omega(e,i)=\bigl(\alpha_{u(e,i)},\beta_e\bigr)\in\Omega.
\]
We need the vertex groups to be small and the incidence labels not to be too crowded.

\begin{lemma}[Balanced labels]\label{lem:labels}
Suppose $N^2+nd^2=o(v)$. With probability $1-o(1)$, the random labels satisfy
\begin{align}
  \bigl|\{u\in V:\alpha_u(t)=g\}\bigr|
     &\le\frac{2v}{d}
     &&(t\in[n],\ g\in[d]),\label{eq:group-bound}\\
  \bigl|\{(e,i)\in\mathcal I:\omega(e,i)=\omega\}\bigr|
     &\le\frac{6v}{N}
     &&(\omega\in\Omega).\label{eq:load-bound}
\end{align}
The conditions can be checked in polynomial time, so repeatedly sampling until they hold gives a Las Vegas construction of expected polynomial cost.
\end{lemma}

\begin{proof}
Let $X_\omega$ count the incidences with label $\omega$, and set $m_0=|\mathcal I|=3v$. Then $\E X_\omega=m_0/N$ and
\[
  \sum_\omega(X_\omega-m_0/N)^2
  =\sum_{\iota,\iota'\in\mathcal I}
      \one\{\omega(\iota)=\omega(\iota')\}
     -\frac{m_0^2}{N}.
\]
Two incidence labels are independent unless the incidences share a graph vertex or a graph edge. Since all degrees are three, only $O(v)$ ordered pairs share one of these. Independent pairs have collision probability $1/N$; every other probability is at most one. Therefore
\begin{equation}\label{eq:collision-moment}
  \E\sum_\omega(X_\omega-m_0/N)^2=O(v).
\end{equation}
If some $X_\omega>2m_0/N$, this sum exceeds $(m_0/N)^2$. Markov's inequality bounds the failure probability of~\eqref{eq:load-bound} by $O(N^2/v)$.

Next let $Y_{t,g}=|\{u:\alpha_u(t)=g\}|$. Independence of the vertex labels gives
\begin{equation}\label{eq:group-moment}
  \E\sum_{t,g}(Y_{t,g}-v/d)^2
     =nv(1-1/d)\le nv.
\end{equation}
If any $Y_{t,g}>2v/d$, this sum exceeds $(v/d)^2$. Thus the failure probability of~\eqref{eq:group-bound} is at most $nd^2/v$. The sum of the two failure probabilities tends to zero.
\end{proof}

This second-moment argument is the randomized form of the balancing construction in~\cite[Section~4.4]{OAI26}. From now on, fix labels that pass the two checks.

\subsection{Copies of the auxiliary array}

Let $h=\max_\omega X_\omega$. Take $h$ copies of $\Omega$ and place each incidence $(e,i)$ at coordinate $\omega(e,i)$ of one copy, placing incidences with the same label in different copies. Write $j(e,i)$ for its copy. Fill its position with the formal variable $x_{u(e,i)}$, and put zero in every unused position. Denote the resulting vector in copy $j$ by
\[
  z^{(j)}(x)\in\Q^\Omega.
\]
The load bound gives
\begin{equation}\label{eq:copies-size}
  hN\le6v.
\end{equation}
In particular the total number of auxiliary positions is $O(v)$.

These are repeated positions for the original variables, not new Boolean variables: all positions containing $x_u$ always have the same value. Apply the replacement form in the copy containing each incidence:
\begin{equation}\label{eq:L}
  L_{e,i}(T,x)
     =K_{\omega(e,i)}\bigl(T,z^{(j(e,i))}(x)\bigr).
\end{equation}
Lemma~\ref{lem:replacement} immediately gives
\begin{equation}\label{eq:L-properties}
  L_{e,i}(0,x)=x_{u(e,i)},
  \qquad
  \deg_TL_{e,i}\le b.
\end{equation}

\subsection{Splitting the measurements by group}

Keep the measurements $Cz^{(j)}(x)$ for every copy $j$. There are $hs_0\le h\rho N\le6\rho v$ of them. At point $t$, the graph-vertex groups are
\[
  V_{t,g}=\{u\in V:\alpha_u(t)=g\}
  \qquad(g\in[d]).
\]
For each measurement $\ell(x)$, split it into the sum of its restrictions to these groups:
\[
  \ell(x)=\sum_{g=1}^d\ell|_{V_{t,g}}(x|_{V_{t,g}}).
\]
This splitting is important: fixing a total such as $x_u+x_w$ would still couple groups containing $u$ and $w$. Fixing the separate group contributions gives independent conditions within the groups.

Collect the restricted measurements on group $g$ as the rows of an integer matrix $C_{t,g}$. Including zero rows, the total number of measurements at a point is
\begin{equation}\label{eq:s}
  s=\sum_{g=1}^d\#\operatorname{rows}(C_{t,g})
    =dhs_0\le6\rho dv.
\end{equation}
Every row of $C$ has at most $N$ nonzero entries, each equal to $1$ or $-1$. Substitution of graph variables, combination of repeated occurrences, and restriction to a group cannot increase the absolute coefficient sum. Hence every row of $C_{t,g}$ has absolute coefficient sum at most $N$. On a Boolean assignment, each measurement therefore takes an integer value in $[-N,N]$.

\Needspace{10\baselineskip}
\begin{lemma}[Locality after fixing measurements]\label{lem:locality}
Fix $t\in[n]$. After the values of all $C_{t,g}x|_{V_{t,g}}$ have been fixed, both forms $L_{e,1}(t,x)$ and $L_{e,2}(t,x)$ depend only on the variables in $V_{t,\beta_e(t)}$.
\end{lemma}

\begin{proof}
The group-restricted measurements determine each total $Cz^{(j)}(x)$. By Lemma~\ref{lem:replacement}, the only other coordinates needed to evaluate $L_{e,i}(t,x)$ have first group label $\beta_e(t)$. Every occupied auxiliary coordinate containing $x_u$ has first label $\alpha_u$, so these coordinates contain only variables from $V_{t,\beta_e(t)}$. Both endpoint occurrences of $e$ have second label $\beta_e$ and therefore use the same group.
\end{proof}

This completes the transfer from auxiliary coordinates to graph incidences; it is the specialization of~\cite[Section~4.5]{OAI26} used here.

\section{A polynomial with easily evaluated points}

Define
\begin{equation}\label{eq:H}
  H(T)=\sum_{x\in\{0,1\}^V}
       \prod_{e\in E}\bigl(1-L_{e,1}(T,x)L_{e,2}(T,x)\bigr).
\end{equation}
At zero the replacements restore the original variables, while each edge contributes degree at most $2b$. Thus
\begin{equation}\label{eq:H-degree}
  H(0)=Z(G),\qquad \deg H\le2|E|b=3vb.
\end{equation}
At a nonzero point $t\in[n]$, Lemma~\ref{lem:locality} makes the factors separate once the group measurements are fixed.

Here is the evaluation procedure explicitly. Write $x_g=x|_{V_{t,g}}$ and let
\[
  F_{t,g}(x)=\prod_{e:\,\beta_e(t)=g}
            \bigl(1-L_{e,1}(t,x)L_{e,2}(t,x)\bigr).
\]
Enumerate all tuples of possible measurement values
\[
  y=(y_1,\ldots,y_d),\qquad
  y_g\in\{-N,\ldots,N\}^{\#\operatorname{rows}(C_{t,g})}.
\]
For each group put
\[
  \mathcal X_g(y_g)
    =\{x_g\in\{0,1\}^{V_{t,g}}:C_{t,g}x_g=y_g\}.
\]
If some $\mathcal X_g(y_g)$ is empty, skip the tuple. Otherwise choose one representative $\bar x_g\in\mathcal X_g(y_g)$ for every group. To evaluate $F_{t,g}$ on a local assignment $x_g$, combine $x_g$ with the representatives in the other groups. Locality guarantees that the chosen representatives do not affect the value; denote it by $F_{t,g}(x_g;y)$.

The assignments with measurement tuple $y$ form the Cartesian product $\prod_g\mathcal X_g(y_g)$. Distributivity therefore gives
\begin{equation}\label{eq:separation}
  H(t)=\sum_y\prod_{g=1}^d
       \left(\sum_{x_g\in\mathcal X_g(y_g)}F_{t,g}(x_g;y)\right).
\end{equation}
Every Boolean assignment has exactly one tuple of measurement values, so the formula counts its contribution exactly once.

There are at most $(2N+1)^s$ tuples. For each tuple, finding representatives and summing within the groups examines at most
\[
  2\sum_{g=1}^d2^{|V_{t,g}|}\le2d\,2^{2v/d}
\]
local assignments. Consequently an evaluation costs, up to polynomial factors,
\begin{equation}\label{eq:evaluation-cost}
  (2N+1)^s2^{2v/d}.
\end{equation}

\paragraph{Two extensions of the same procedure.}
We may require any prescribed subset of the Boolean variables to equal one: this simply restricts the local summations. We may also add to each input $L_{e,i}(t,x)$ a fixed element of a commutative ring, independent of $x$. Such shifts do not alter the dependence on other groups, so separation still holds. In particular, the same procedure works over $\Q[z]/(z^{q+1})$, with fixed polynomial shifts, at polynomial overhead in $q$. The representatives used to evaluate a factor need only satisfy the measurements, not the additional fixed-bit restrictions.

\section{Taylor recovery by standard algebraic tools}

We know how to evaluate $H(T)$ at $T=1,\ldots,n$, but
$\deg H\le3vb$, so ordinary interpolation is insufficient. We use three familiar tools: Hermite interpolation, formal Taylor expansion (equivalently Hasse derivatives), and M\"obius inversion on the Boolean lattice. Closely related derivative-recovery methods appear in Bhargava--Ghosh--Kumar--Mohapatra~\cite[Lemmas~4.10 and~6.2]{BGKM23}; subset M\"obius transforms have long been used in exact graph algorithms, for example by Bj\"orklund--Husfeldt--Kaski--Koivisto~\cite{BHKK08}. Here they allow us to use the \emph{same} separated summation algorithm for all the required derivatives.

\subsection{How much Taylor data is enough?}

Set
\begin{equation}\label{eq:q}
  q=\left\lfloor\frac{3vb}{n}\right\rfloor.
\end{equation}
We will compute
\[
  H(t+z)\pmod{z^{q+1}}
  \qquad(t=1,\ldots,n).
\]
These data determine $H$: if two polynomials of degree at most $3vb$ have the same first $q+1$ Taylor coefficients at every $t$, their difference is divisible by
\[
  \prod_{t=1}^n(T-t)^{q+1},
\]
whose degree $n(q+1)$ exceeds $3vb$. Hermite interpolation therefore recovers $H(0)$ using polynomially many rational operations.

The problem is that the deformed factors at $t+z$ no longer separate across the groups at $t$. We keep the changes as independent formal inputs.

\subsection{Give the changes their own variables}

Fix $t$. Let $x\in\{0,1\}^{V}$ be the Boolean assignment being summed over, and introduce a separate formal vector $X=(X_u)_{u\in V}$. Define
\begin{equation}\label{eq:deltaL}
  \Delta L_{e,i}(z,X)
    =L_{e,i}(t+z,X)-L_{e,i}(t,X)
\end{equation}
and
\begin{equation}\label{eq:Ftx}
  F_{t,x}(X,z)
  =\prod_{e\in E}
   \left(1-
    \bigl(L_{e,1}(t,x)+\Delta L_{e,1}(z,X)\bigr)
    \bigl(L_{e,2}(t,x)+\Delta L_{e,2}(z,X)\bigr)
   \right).
\end{equation}
Setting $X=x$ restores the shifted inputs, so
\begin{equation}\label{eq:diagonal-target}
  H(t+z)=\sum_{x\in\{0,1\}^V}F_{t,x}(x,z).
\end{equation}
But if we fix $X$, every $\Delta L_{e,i}(z,X)$ becomes a constant polynomial shift, independent of $x$. Then the separated computation from Section~6 still works.

Every $\Delta L_{e,i}(z,X)$ is linear in $X$ and divisible by $z$. Therefore every occurrence of an $X_u$ contributes a factor of $z$, and
\begin{equation}\label{eq:degree-Taylor}
  \deg_X[z^j]F_{t,x}(X,z)\le j.
\end{equation}
In particular, modulo $z^{q+1}$, the polynomial $F_{t,x}(X,z)$ has degree at most $q$ in $X$. We now eliminate the diagonal substitution $X=x$ by Boolean finite differences.

\subsection{Boolean discrete Taylor expansion}

For a polynomial $P(X)$ and a set $A\subseteq V$, write
\[
  \Delta_A P(0)
    :=\sum_{B\subseteq A}(-1)^{|A|-|B|}P(\one_B),
\]
where $\one_B$ is the Boolean vector with support $B$.
This is the $A$th discrete derivative of $P$ at zero. M\"obius inversion says that on Boolean inputs $y$,
\begin{equation}\label{eq:newton}
  P(y)=\sum_{A\subseteq V}\Delta_A P(0)
                   \prod_{u\in A}y_u.
\end{equation}
If $\deg P\le q$, only sets $A$ of size at most $q$ appear.

\begin{lemma}[Diagonal-sum identity]\label{lem:diagonal}
Let $\mathcal R$ be a commutative ring. For each $x\in\{0,1\}^{V}$, let $P_x(X)$ be a polynomial over $\mathcal R$ of degree at most $q$. Then
\begin{equation}\label{eq:diagonal}
  \sum_xP_x(x)
    =\sum_{\substack{A\subseteq V\\|A|\le q}}
       \sum_{x:\,x_u=1\ (u\in A)}\Delta_A P_x(0).
\end{equation}
\end{lemma}

\begin{proof}
Replace every positive power of $X_u$ by $X_u$ to obtain the multilinear representative of each $P_x$. The standard M\"obius-inversion formula~\eqref{eq:newton} gives its coefficients. Upon setting $X=x$, the monomial $\prod_{u\in A}x_u$ selects exactly the assignments whose bits in $A$ are all one. Sum over $x$ and interchange the two sums.
\end{proof}

Expanding $\Delta_A$ yields the form directly used by the algorithm:
\begin{equation}\label{eq:diagonal-expanded}
  \sum_xP_x(x)
    =\sum_{\substack{A\subseteq V\\|A|\le q}}
       \sum_{B\subseteq A}(-1)^{|A|-|B|}
       \sum_{x:\,x_u=1\ (u\in A)}P_x(\one_B).
\end{equation}
This is Lemma~3.3 of~\cite{OAI26}; its proof is exactly the ordinary discrete Taylor formula.

\subsection{Computing the Taylor coefficients}

Apply~\eqref{eq:diagonal-expanded} with
$P_x(X)=F_{t,x}(X,z)\bmod z^{q+1}$ over
$\mathcal R=\Q[z]/(z^{q+1})$. By~\eqref{eq:degree-Taylor},
\begin{equation}\label{eq:taylorsum}
  H(t+z)\equiv
   \sum_{\substack{A\subseteq V\\|A|\le q}}
   \sum_{B\subseteq A}(-1)^{|A|-|B|}
   \sum_{x:\,x_u=1\ (u\in A)}F_{t,x}(\one_B,z)
   \pmod{z^{q+1}}.
\end{equation}
Each innermost sum is an instance of the separated computation: $X=\one_B$ fixes the correction polynomial, while the conditions $x_u=1$ for $u\in A$ restrict the allowed assignments within their groups. In particular, we have not needed to construct a polynomial in all the formal variables $X$.

The number of pairs $(A,B)$ is
\begin{equation}\label{eq:number-pairs}
  \mathcal C_q=\sum_{j=0}^{\min(q,v)}2^j\binom vj.
\end{equation}
For $1\le q\le v/2$,
\begin{equation}\label{eq:number-pairs-bound}
  \mathcal C_q\le(q+1)\left(\frac{2\mathrm e v}{q}\right)^q
  =2^{O(q\log(2v/q))}.
\end{equation}
Thus all the necessary Taylor coefficients at one point are computable at the cost of only this additional factor. Computing them at every point and performing Hermite interpolation gives the exact value $H(0)$.

For context, Barvinok's Taylor method and its graph-polynomial refinements by Patel--Regts~\cite{PR22} also exploit low-order coefficients, but use zero-free regions for \emph{approximate} counting. Here Hermite interpolation recovers the whole polynomial \emph{exactly}. The device that makes it efficient is the separation-preserving use of the second vector $X$.

\section{Running time and completion of the proof}

Suppose the auxiliary parameters are polynomially bounded in $v$ and $b/n=o(1)$. Then eventually $1\le q\le v/2$. By~\eqref{eq:s},~\eqref{eq:evaluation-cost}, and~\eqref{eq:number-pairs-bound}, the total time, up to polynomial factors, is
\begin{equation}\label{eq:total-cost}
  2^{O\left(
     \frac vd
     +\rho dv\log(2N+1)
     +v\frac bn\log\frac{2n}{b}
   \right)}.
\end{equation}
The three terms count local Boolean assignments, measurement values, and Boolean finite differences. The number of interpolation points and the exact Hermite interpolation itself contribute polynomial factors.

Let $L=\lceil\log v\rceil$. To avoid log-log bookkeeping, choose simply
\begin{equation}\label{eq:parameters}
  \boxed{
  d=\lfloor L^{1/4}\rfloor,
  \qquad n=\lfloor L^{4/5}\rfloor,
  \qquad b=\lceil L^{1/2}\rceil.
  }
\end{equation}
These parameters satisfy $d\ge2$ and $32\le b\le n/6$ for all sufficiently large $v$. The typical-weight lemma gives
\begin{equation}\label{eq:rho-size}
  \rho\le2\exp\left(-\Omega(L^{1/5})\right),
\end{equation}
where we use $b^2/n=\Theta(L^{1/5})$. Moreover,
\begin{equation}\label{eq:N-size}
  \log N=2n\log d=O(L^{4/5}\log L)=o(L).
\end{equation}
Hence $N=v^{o(1)}$; in particular $N^2+nd^2=o(v)$, so the randomized labeling lemma applies and all the auxiliary matrices have polynomial size.

Finally, the three terms of~\eqref{eq:total-cost} are bounded by
\begin{align*}
  \frac vd&=O(v/L^{1/4}),\\
  \rho dv\log(2N+1)&=v\exp(-\Omega(L^{1/5}))L^{O(1)}
                     =o(v/L^{1/4}),\\
  v\frac bn\log\frac{2n}{b}
    &=O\left(\frac{v\log L}{L^{3/10}}\right)
     =O(v/L^{1/4}).
\end{align*}
This proves the time bound in Theorem~\ref{thm:main}. A sample labeling is checked before use, succeeds with probability $1-o(1)$, and can be resampled independently on failure; all subsequent steps are exact. Small input sizes are handled by exhaustive search.

We omit the standard exact-arithmetic estimates and the proof of polynomial space. The interpolation polynomials have rational coefficients of polynomial bit length; after clearing common denominators, even exponentially many summands can be accumulated with polynomially many bits. The loops are sequential and store only polynomially many Taylor coefficients. These details are carried out in~\cite[Lemma~4.6 and Appendix~B.4]{OAI26}.

Conditional expectations derandomize the auxiliary labeling, as discussed at the start, yielding a deterministic algorithm with the same asymptotic time bound. Liu--Chen's result~\cite{LC24} then gives the stated contradiction to $\#\mathrm{ETH}$, and hence to ETH. \qed

\medskip
\noindent\textbf{Perspective.}
The spectral approximation is not used to approximate the count. It makes $I-M$ have small rank; the exceptional eigendirections are retained as exact integer measurements. After these measurements are fixed, the deformed edge factors separate. Ordinary finite differences and Hermite interpolation then recover the original partition function exactly.

\begin{thebibliography}{BGKM23}

\bibitem[AW15]{AW15}
Josh Alman and Ryan Williams.
\newblock Probabilistic Polynomials and Hamming Nearest Neighbors.
\newblock In \emph{56th Annual IEEE Symposium on Foundations of Computer Science (FOCS)}, 2015.
\newblock Lemma~3.1.
\newblock \url{https://arxiv.org/abs/1507.05106}.

\bibitem[BGL06]{BGL06}
Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton.
\newblock Symmetric Polynomials over $\mathbb Z_m$ and Simultaneous Communication Protocols.
\newblock \emph{Journal of Computer and System Sciences} 72(2):252--285, 2006.
\newblock \url{https://doi.org/10.1016/j.jcss.2005.06.007}.

\bibitem[BGKM23]{BGKM23}
Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra.
\newblock Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications.
\newblock \emph{Journal of the ACM} 70(6), Article 42, 2023.
\newblock Lemmas~4.10 and~6.2.
\newblock \url{https://doi.org/10.1145/3625226}.

\bibitem[BHKK08]{BHKK08}
Andreas Bj\"orklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.
\newblock Trimmed M\"obius Inversion and Graphs of Bounded Degree.
\newblock In \emph{STACS 2008}, pages 85--96, 2008.
\newblock \url{https://doi.org/10.4230/LIPIcs.STACS.2008.1336}.

\bibitem[LC24]{LC24}
Ying Liu and Shiteng Chen.
\newblock Sub-Exponential Time Lower Bounds for \#VC and \#Matching on 3-Regular Graphs.
\newblock In \emph{41st Symposium on Theoretical Aspects of Computer Science (STACS)}, LIPIcs 289, 49:1--49:18, 2024.
\newblock Theorem~11.
\newblock \url{https://doi.org/10.4230/LIPIcs.STACS.2024.49}.

\bibitem[OAI26]{OAI26}
OpenAI.
\newblock \emph{The Exponential Time Hypothesis Is False}.
\newblock Manuscript dated October 17, 2026; revised October 25, 2026.
\newblock Sections~2--4 and Appendix~B.

\bibitem[PR22]{PR22}
Viresh Patel and Guus Regts.
\newblock Approximate Counting Using Taylor's Theorem: A Survey.
\newblock \emph{Bulletin of the EATCS}, 2022.
\newblock \url{https://arxiv.org/abs/2212.08143}.

\bibitem[Sri13]{Sri13}
Srikanth Srinivasan.
\newblock On Improved Degree Lower Bounds for Polynomial Approximation.
\newblock In \emph{FSTTCS 2013}, LIPIcs 24, pages 201--212, 2013.
\newblock Lemma~14.
\newblock \url{https://doi.org/10.4230/LIPIcs.FSTTCS.2013.201}.

\bibitem[Vio09]{Vio09}
Emanuele Viola.
\newblock On the Power of Small-Depth Computation.
\newblock \emph{Foundations and Trends in Theoretical Computer Science} 5(1):1--72, 2009.
\newblock Section~1.2.3, including an argument communicated by Avi Wigderson.
\newblock \url{https://doi.org/10.1561/0400000033}.

\end{thebibliography}
\end{document}