==== TABLE OF CONTENTS ====
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//01-introduction.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//02-geometry.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//03-seed.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//04-cones.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//05-bands.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//06-comparison.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//07-regret.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//08-accuracy.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//09-numerics.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//10-work.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//connection-cost.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//macros.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//paper.tex
An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//references.bib
===========================

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//01-introduction.tex ====
\section{Introduction}\label{sec:intro}
The unit-cost edit distance $\ED(x,y)$ is the minimum number of
single-symbol insertions, deletions and substitutions that transform a string
$x$ into a string $y$. All three operations have cost one. The strings are
stored explicitly; write $N=|x|+|y|$. Their symbols are integer labels of
polynomial magnitude in $N+2$, stored in words of $O(\log(N+2))$ bits.
There is no bound on the alphabet size independent of $N$.

An approximation scheme receives a rational $\varepsilon\in(0,1)$ and
estimates the distance multiplicatively. Its guarantee must therefore include
returning zero when the two strings are equal. We prove the following result.

\begin{theorem}\label{thm:main}
There is one uniform randomized algorithm that, given $x,y$ and a rational
$\varepsilon\in(0,1)$, returns a nonnegative integer $\widehat D$ such that
\[
 \Pr\bigl[\ED(x,y)\le \widehat D\le(1+\varepsilon)\ED(x,y)\bigr]
 \ge \frac23.
\]
For every fixed rational $\varepsilon$, its worst-case expected running time
on strings of total length $N$ is $N^{1+o(1)}$ as $N\to\infty$ on the
logarithmic-word RAM. The expectation is over internal randomness only,
and the bound includes input processing, preprocessing, numerical work,
random sampling and all data-structure operations. Equal strings return zero
deterministically.
\end{theorem}

The program is uniform in the accuracy input. The asymptotic assertion is
pointwise in each fixed rational accuracy: its constants and the threshold
at which the bound applies may depend on $\varepsilon$. We do not assert
polynomial dependence on $1/\varepsilon$ or a joint bound when the accuracy
varies with $N$. The output is a distance estimate; no edit-script
reconstruction is needed.

The algorithm uses exact computation below an accuracy-dependent input-length
threshold. Section~\ref{sec:geometry} gives the finite input convention and
fallback rules; their thresholds are very large, so the result is an
asymptotic approximation scheme.

\subsection{Context and approach}
Edit distance originates in the study of errors in transmitted strings,
including Levenshtein's binary codes for insertions, deletions and bit
flips~\cite{Levenshtein1966}. The dynamic program of Wagner and
Fischer~\cite{WagnerFischer1974} computes the minimum cost of insertions,
deletions and substitutions in quadratic time. Masek and
Paterson~\cite{MasekPaterson1980} applied block tabulation to obtain a
logarithmic speedup for fixed alphabets and suitable fixed costs.
Distance-sensitive exact algorithms offer another route when few edits
are needed: Ukkonen~\cite{Ukkonen1985} developed bounded-distance methods,
and Landau and Vishkin~\cite{LandauVishkin1988,LandauVishkin1989} combined
furthest-reaching states with fast matching queries. Myers's related
difference algorithm~\cite{Myers1986} treats insertion--deletion scripts.
For unrestricted exact computation, Backurs and
Indyk~\cite{BackursIndyk2018} showed that a strongly subquadratic
deterministic algorithm
would refute the Strong Exponential Time Hypothesis. That lower bound
does not rule out fixed-factor approximation.

Approximation algorithms progressively improved the accuracy available
with substantially less work. In the following historical comparisons,
write $n$ for a common upper bound on the string lengths.
Batu and coauthors~\cite{BatuEtAl2003}
gave sublinear tests for fixed alphabets that distinguish sufficiently
small distance from linear distance. For general pairs, Bar-Yossef, Jayram, Krauthgamer and
Kumar~\cite{BarYossefEtAl2004} obtained an $n^{3/7}$ approximation in
quasi-linear time; Batu, Erg\"un and
Sahinalp~\cite{BatuErgunSahinalp2006} improved the factor to
$n^{1/3+o(1)}$. For binary strings, Ostrovsky and
Rabani~\cite{OstrovskyRabani2007}
constructed a low-distortion embedding into $\ell_1$, and Andoni and
Onak~\cite{AndoniOnak2012} obtained an efficiently computable
$2^{\widetilde O(\sqrt{\log n})}$ approximation in $n^{1+o(1)}$ time.
Andoni, Krauthgamer and Onak~\cite{AndoniKrauthgamerOnak2010} then
achieved a $(\log n)^{O(1/\xi)}$ factor in $n^{1+\xi}$ time for each
fixed $\xi>0$, using a hierarchical alignment representation and
nonuniformly allocated precisions.

The next advances reached constant factors. Chakraborty, Das,
Goldenberg, Kouck\'y and Saks~\cite{ChakrabortyEtAl2020} gave a
constant-factor approximation in $\widetilde O(n^{12/7})$ time.
Brakensiek and Rubinstein~\cite{BrakensiekRubinstein2020} and Kouck\'y
and Saks~\cite{KouckySaks2020} independently obtained near-linear
exponents for sufficiently far input pairs, with a material additive
error on general pairs. Andoni and Nosatzki~\cite{AndoniNosatzki2020}
removed that restriction: for every fixed $\xi>0$, their algorithm
gives an approximation factor depending only on $\xi$ in
$O(n^{1+\xi})$ time. The factor depends on the exponent parameter;
this is not an approximation scheme with error tending to zero.
For accuracy arbitrarily close to one, Mao and
Rubinstein~\cite[Theorem~6.1]{MaoRubinstein2026} recently obtained a
randomized $(1+\varepsilon)$ approximation in
$n^2/2^{\log^{\Omega(1)}n}$ time for every fixed positive
$\varepsilon$.

The issue addressed here is how to retain fixed $(1+\varepsilon)$
accuracy while reducing the expected total work to $N^{1+o(1)}$.
Recursive interval decompositions, economical evaluation of local
distances, and accounting along an optimal alignment have substantial
precedent in the algorithms above. In our refinement, unrestricted recursive evaluation of child distances would consume
the available time even if the resulting numerical error were small. We therefore need both a narrow family that
contains a suitable comparison alignment and a bound on the number of
child distances actually evaluated.

For the initial estimates we adapt the shift tree and precision sampling
of Andoni, Krauthgamer and
Onak~\cite{AndoniKrauthgamerOnak2010,AndoniKrauthgamerOnak2011}.
The refinement is related to Mao and Rubinstein's use of multiscale
deviation to constrain alignment paths before sampling
\cite{MaoRubinstein2026}. Here we measure the alignment's changes in relative position using
preliminary cost estimates as weights. A telescoping bound on their
variation controls the total cost of places where the prediction fails.
An entropy-regularized prediction rule, within the framework of
Rakhlin and Sridharan~\cite{RakhlinSridharan2013}, then controls the
accumulated error where the predictions can be used. We implement its
optimization by a finite Frank--Wolfe procedure
\cite{FrankWolfe1956,Jaggi2013}. The specialized geometric, probabilistic
and numerical guarantees are proved in this paper.

Two related comparisons concern different requirements on the output or
the edit costs. A single $\ell_1$ embedding of all binary strings up to a
length bound must incur growing distortion
\cite[Theorem~1.1]{OpenAIEditDistortion2026}. Our algorithm estimates the
distance of the supplied pair and does not construct such a common
embedding. Recent algorithms for metric-weighted edit costs obtain
$(3+\varepsilon)$ approximation in strongly subquadratic time
\cite{MaderTavasoliWang2026,DasKipouridisKociumaka2026}; their cost model
is broader than the unit-cost model treated here.

\subsection{Proof overview}
Recursively partition the first string into a tree of intervals, ending at
intervals of length at most one. An interval state consists of a source
interval $I$ and a target interval in the second string; its true cost is
the edit distance between the two substrings. An action at a nonleaf
assigns one target interval to each source child. We charge the sum of
the child estimates together with penalties for gaps or overlaps between
successive target endpoints and at the two outer endpoints. These
penalties let us compare nearby actions without requiring their target
intervals to join exactly.

\paragraph{Estimates that can be requested adaptively.}
The initial seed is an integer table whose entries give coarse upper
approximations to all interval-state costs. Although the algorithm evaluates
only requested entries, the accuracy event covers the entire domain:
later queries may depend on earlier random answers. Each initial entry
uses a private random stream, so its expected evaluation cost can also
be bounded conditional on the request that first exposes it. Accuracy
and expected work thus use different probability statements. Successive
refinement passes improve the seed approximation factor.

\paragraph{Predicting where an alignment goes.}
One refinement starts from such a seed. It first propagates estimates
through a wide family of actions and averages the resulting preliminary
tables to obtain cost proxies. At a source cut, the alignment's shift is
the target position minus the source position. The total shift change
divided by the predicted total cost suggests how this shift should evolve
as prefix cost accumulates. Requiring agreement with that prediction
restricts the possible target positions at each cut to a narrow band.
The algorithm computes these bands from the cost proxies alone.

To analyze them, fix optimal alignments and recursively round their child
endpoints. This gives a comparison tree that the algorithm never computes.
A cost-weighted variance measures how far the comparison shifts depart
from the predicted evolution. Its sum telescopes, with additional charges
for disagreements among the cost proxies. Consequently the total cost of
nodes with large discrepancies is controlled. At the other nodes, either
the substring-length difference already accounts for almost all predicted
cost, giving a direct error bound, or the computed band contains the
comparison action.

\paragraph{From a band to a better seed.}
Within a band, an entropy-regularized rule predicts an action using earlier
child values. Shared samples also compare rounded actions across nearby
representatives. The resulting estimates decrease with the refinement
index. After conditioning on complete child tables, the parent samples
retain their prescribed laws, and an online inequality bounds cumulative
excess over the comparison action.
Some intermediate estimates can be smaller than true cost. The analysis
therefore clips them from below at true cost, so an underestimate at one
node cannot cancel an error elsewhere. Summing
over the comparison tree gives a small expected positive error at any
fixed queried state, together with a deterministic multiplicative lower
bound. Independent repetitions, rescaling and medians turn these two
bounds into a simultaneous one-sided seed with a smaller approximation
factor. Repeating this improvement and making one final refinement gives
the desired answer.

\paragraph{Paying for recursive queries.}
A wide search or an optimization step may inspect many actions, but it
reuses previously gathered child values. Only shared group samples,
selected rounded actions and actual online draws require child values
at the current refinement index. Common rounded grids limit the number
of these calls to slightly more than the tree's branching factor.
Along a dependency path, a call either descends the tree at the same
index or decreases an index or pass. Counting these two kinds of steps
bounds the total expected work, including rational arithmetic and exact
sampling, by $N^{1+o(1)}$.

Section~\ref{sec:geometry} fixes the computational model, geometry and
parameters. Sections~\ref{sec:seed}--\ref{sec:bands} construct the tables.
Sections~\ref{sec:comparison} and~\ref{sec:regret} prove the geometric and
probabilistic estimates, and Section~\ref{sec:accuracy} assembles the
accuracy guarantee. Sections~\ref{sec:numerics} and~\ref{sec:work} implement
every operation and complete the running-time proof.
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//01-introduction.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//02-geometry.tex ====
\section{Alignment geometry and computational parameters}\label{sec:geometry}
This section fixes the input conventions and the interval states used
throughout the algorithm. It also records the geometric inequalities that
allow child intervals to be combined even when their target endpoints do
not agree.

\subsection{Paths, states and connection costs}
Index string boundaries starting at zero. An alignment path has steps
$(1,0),(0,1),(1,1)$, of cost one, one, and the indicator that the two
characters on a diagonal step differ. Such a path gives an edit sequence.
Conversely, the original characters that survive an edit sequence occur in
the final string in their original order. Deleting other original
characters, inserting the remaining output characters and changing each
surviving character whose label differs gives an alignment of no greater
cost. Thus minimum alignment cost equals edit distance.

For an interval $I=(l,u]$ of the first string, an interval state is
$(I,q)$, where $q=(q^-,q^+)$ is an integer pair with
$0\le q^-\le q^+\le |y|$. When $I$ is fixed, we also call $q$ a state. Set
\[
 c(I,q)=\ED\bigl(x_{(l,u]},y_{(q^-,q^+]}\bigr),\qquad
 z(I,q)=(q^+-q^-)-(u-l).
\]
An endpoint's \emph{shift} is its target index minus its first-string index.
In particular, $z$ is the change in shift between the two endpoints.
For pairs use $|q-r|_1=|q^--r^-|+|q^+-r^+|$.

\begin{lemma}\label{lem:geometry}
For every interval state, $c(I,q)\ge |z(I,q)|$. Both $c(I,\cdot)$ and
$|z(I,\cdot)|$ are $1$-Lipschitz in the endpoint metric.
If $I$ is partitioned, in order, into $I_1,\ldots,I_m$, and
$\alpha=(s_1,\ldots,s_m)$ is any list of valid child states, define
\[
 \conn_r(\alpha)=|s_1^--r^-|
   +\sum_{i=1}^{m-1}|s_{i+1}^--s_i^+|+|s_m^+-r^+|.
\]
Then
\begin{align}
 c(I,r)&\le\sum_i c(I_i,s_i)+\conn_r(\alpha),\label{eq:connection}\\
 |z(I,r)|&\le\sum_i|z(I_i,s_i)|+\conn_r(\alpha).
 \label{eq:shift-connection}
\end{align}
The connection inequalities also hold for finite target intervals in any
extension of $y$ beyond its stored endpoints.
\end{lemma}
\begin{proof}
Only insertions and deletions change length, proving $c\ge|z|$.
Changing a target substring's endpoints costs at most $|q-r|_1$:
remove or insert endpoint portions if the substrings overlap, and delete
and insert the whole substrings if they are disjoint. The triangle
inequality gives the claim for $c$; the claim for $|z|$ follows from its
formula.

Edit each child to its specified target substring and concatenate the
results. Consider the walk on the target's boundary line that starts at
$r^-$, jumps to $s_1^-$, traverses each child target forward, makes the
successive connecting jumps, and ends at $r^+$. Expand each jump into unit
steps. From this walk choose, in order, one forward crossing of every unit
interval between $r^-$ and $r^+$. Successive first arrivals at the next
boundary give such a choice. The letters on these selected crossings,
in their walk order, form exactly the parent's target substring. Delete
the letters on unselected child crossings, and insert the letters on
selected connecting crossings. By net displacement, the number of
unselected forward crossings equals the number of backward crossings.
All backward crossings belong to connecting jumps, since child targets
are traversed forward. Thus deletions cost at most the total backward
jump length, while insertions cost at most the total forward jump length.
Their sum is $\conn_r(\alpha)$, proving~\eqref{eq:connection}.
This argument uses only the letters at finitely many target positions,
so it also proves the assertion for extensions of $y$.
Finally, sum the signed shift changes of child intervals and connecting
jumps and take absolute values to obtain~\eqref{eq:shift-connection}.
\end{proof}

Figure~\ref{fig:connection-cost} illustrates why the connection term permits
both gaps and overlaps between consecutive child targets.
\input{figures/connection-cost.tex}

\subsection{Uniform access to the accuracy input}
The rational accuracy is supplied in a fixed canonical binary encoding of
its positive numerator and denominator in lowest terms, on a separate
read-only input.
For example, encode a positive integer by its binary length in unary,
a delimiter, and its binary digits, and concatenate the two encodings.
The input is promised to specify $0<\varepsilon<1$. Prefix inspection is
ordinary input access; no numerical operation on the rational is free.

The algorithm first handles equality, empty strings and $|x|\le1$
exactly. These cases require $O(N+1)$ string work. On other inputs define
$H$ as the least power of two at least $\lceil\log_2(N+2)\rceil$, and
$\ell$ as the least power of two at least $\max(1,\log_2 H)$.
Inspect at most $H^2+O(1)$ bits of the accuracy input. If its complete
encoding has not been obtained, use exact alignment dynamic programming.
The unread suffix is neither copied nor addressed. All addresses actually
used for this prefix have $O(\log(N+2))$ bits. If the encoding is obtained,
its integers have $O(H^2)$ bits, and exact arithmetic decides the test
$\ell\varepsilon\ge10$ with polynomial work in $H$.

Use exact dynamic programming also if $\ell<2^{1000}$ or
$\ell\varepsilon<10$. It uses $O((N+1)^2)$ word operations and can store
only two rows. Together with the bounded parameter inspection, this
charges every operation in these branches. For each fixed rational
encoding, the inspection bound eventually exceeds its length, and both
numeric tests eventually pass as $N$ grows. Thus the exact branches affect
only a bounded range of $N$ for each fixed $\varepsilon$. They preserve
the uniform algorithm and its approximation guarantee on that range.
No assertion about efficient joint dependence on encoding length or
$1/\varepsilon$ is needed.

\subsection{Parameters and the fixed interval tree}
All remaining arguments concern the large-input branch. Logarithms with
subscript two are binary, and $\ln$ denotes the natural logarithm.
The coarse estimator and interval tree use the branching factors $B$ and
$M$ below. The factor $A_{\rm init}$ is the initial seed accuracy, $F$
controls its reduction across passes, and $P$ controls endpoint-grid
resolution:
\begin{align*}
 p_*&=\left\lfloor(\log_2\ell)^{1/4}\right\rfloor,
 &B&=H^{p_*},&A_{\rm init}&=H^{p_*+4},\\
 M&=2^{\lfloor(\log_2 H)/20\rfloor},
 &P&=H^{p_*+20},&F&=\ell.
\end{align*}
The counts $T$ and $S$ govern preliminary propagation and refinement
iterations, respectively. The slopes $L_0$ and $L$ penalize changes in
target endpoints:
\[
 T=2^{\lceil(3/4)\log_2H\rceil},\qquad S=H/\ell^2,
 \qquad L_0=32F,\qquad L=128F.
\]
Finally, fix the error tolerances and the sampling and optimization
parameters. Their roles are specified at the corresponding constructions:
\begin{align*}
 \delta&=\ell^{-10},&\kappa&=\tau=\ell^{-4},
 &\theta&=\ell^{-40},\\
 \gamma&=\ell^{-20},&\eta&=\ell^5,&Q_1&=\ell^{80}.
\end{align*}
The essential separation is between $H=\Theta(\log(N+2))$ and
$\ell=\Theta(\log H)$: the branching factors and grid resolutions are
powers of $H$, while the tolerances are powers of $\ell$. The inequalities
below quantify the slack available between these scales.

Every integer parameter here is computable using bit lengths and integer
tests. For example, $p_*$ is the largest integer whose fourth power is
at most the integer $\log_2\ell$. The displayed fractional powers and
logarithms require no real-arithmetic oracle. All parameters used as dyadic
grid spacings are powers of two, and $S$ is a positive integer in this
branch.

We will repeatedly use the generous bounds
\begin{equation}\label{eq:parameter-slack}
 H\ge2^{\ell/2},\qquad \ell^{200}\le H^{1/100},\qquad
 p_*+21\le\sqrt\ell.
\end{equation}
The first follows from the definition of $\ell$; the other two follow at
$\ell\ge2^{1000}$ and become stronger as $\ell$ increases. More explicitly,
$200\log_2\ell\le\ell/200$ and
$(\log_2\ell)^{1/4}+21\le\sqrt\ell$ hold at this cutoff, and their
right sides thereafter grow faster. Factors polynomial in $\ell$ and
$p_*$ will consequently be much smaller than any fixed positive power
of $H$ needed below.

Partition $x$ into a complete $M$-ary tree of height
\[
 J=\left\lceil\log_M\max(1,|x|)\right\rceil.
\]
At a node $(l,u]$ use cuts
$l_i=l+\lfloor i(u-l)/M\rfloor$, $0\le i\le M$.
Empty intervals are allowed, and node labels distinguish repeated
intervals. Nodes need only be generated when requested. At depth $j$ the
width is at most $\lceil|x|/M^j\rceil$, and leaves have width at most one.
The parameters give
\begin{equation}\label{eq:tree-bounds}
 J\le100H/\ell,\qquad M^J\le M\max(1,|x|).
\end{equation}
Indeed $\log_2M\ge (\log_2H)/20-1$ and
$\log_2H\ge\ell/2$, whereas $\log_2|x|\le H$.
The second bound follows directly from the ceiling defining $J$.

At a leaf of width zero the exact cost is the target length. At a leaf
containing one character, the cost is one for an empty target, and otherwise
is the target length minus the indicator that this character occurs there.
Sort the pairs (symbol, position) of $y$ lexicographically by comparison
sorting. A binary search then tests occurrence in any target interval in
$O(\log(N+2))$ time, with $O(N\log(N+2))$ preprocessing work and linear
storage. The word-label assumption makes each comparison a bounded number
of word operations. Fresh padding symbols used later can be represented by
a tag together with a label; no search for an unused alphabet value is
needed.

All subsequent tables are indexed by this fixed tree and valid endpoint
pairs. The total domain is polynomial in $N+2$: there are at most
$2M^J$ nodes and at most $(|y|+1)^2$ pairs per node. A simultaneous
probability guarantee over this domain is meaningful even though the
algorithm will evaluate only a small part of it.
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//02-geometry.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//03-seed.tex ====
\section{Simultaneous coarse estimates}\label{sec:seed}

The refinement will need an integer estimate at every interval state, including
states chosen adaptively by later computations.  We construct these estimates
as a random table, while evaluating only the entries that are requested.  The
construction builds on tree and precision-sampling ideas of Andoni,
Krauthgamer, and Onak~\cite{AndoniKrauthgamerOnak2010}; the complete bounds
needed here are proved below.

\begin{theorem}[Initial estimates]\label{thm:seed}
With the parameters and labeled interval tree of Section~\ref{sec:geometry},
there is a lazily evaluated random table $U^{(0)}(I,q)$ of integers in $[0,N]$
such that, with probability at least $0.99$, simultaneously at every state,
\begin{equation}\label{eq:seed-guarantee}
 c(I,q)\le U^{(0)}(I,q)\le A_{\mathrm{init}}c(I,q).
\end{equation}
Every zero-cost state has value zero on every execution.  Conditional on any
first request for an entry and the previously exposed randomness, its expected
evaluation cost is at most $(1+|I|)2^{o(H)}$, uniformly in the state.  This cost
bound includes arithmetic and random sampling and does not require
\eqref{eq:seed-guarantee} to hold.
\end{theorem}

\subsection{A deterministic shift tree}

The hierarchical representation below is an adaptation of the
E-distance of Andoni, Krauthgamer and Onak~\cite[Definition~3.2 and
Theorem~3.3]{AndoniKrauthgamerOnak2010}. We prove its precise bounds here,
including the treatment of unequal lengths, empty intervals and bounded
integer shifts.

Fix one state and write $n_x=|I|$, $n_y=q^+-q^-$, and $c=c(I,q)$.  If
$n_y>2n_x$, return $n_y$: the bounds $n_y-n_x\le c\le n_y$ give the required
factor two.  Otherwise
test equality directly and return zero when the strings agree.  These steps
cost $O(1+n_x)$, since in the branch requiring character comparisons
$n_y\le2n_x$.  They include the case $n_x=0$.

For the remaining case, pad the shorter string at its right end with a fresh
tagged symbol to obtain two strings of the same length $n\le2n_x$.  Denote their
distance by $d$.  The length gap is at most $c$, so $d\le2c$.  Conversely,
remove padding from any padded alignment.  A diagonal joining padding to a
real character has cost one and can be replaced by an insertion or deletion
of the same cost; other operations consuming padding can be removed.  Hence
\begin{equation}\label{eq:padding-comparison}
 1\le c\le d\le2c,\qquad 1\le n\le N,\qquad d\le n.
\end{equation}
The last bound follows by substituting characters position by position.

For each dyadic guess
\[
 k\in\{1,2,4,\ldots,2^{\ceil{\log_2 n}}\},
\]
split the first padded string in a complete balanced $B$-ary tree of depth
$D_0=\ceil{\log_B n}$.  Its leaves have width zero or one.  Allowed shifts are
the integers in $[-k,k]$.  At a width-one leaf $w$ starting at position $j$,
let $T_w(v)$ be the mismatch indicator between its character and position
$j+1+v$ of the second padded string.  A position outside the latter string
has a virtual symbol that always mismatches.  At a width-zero leaf put
$T_w(v)=0$.  At an internal node define
\begin{equation}\label{eq:coarse-tree}
 T_w(v)=\sum_{i=1}^B\min_{v'\in[-k,k]\cap\Z}
       \{T_{w_i}(v')+2|v-v'|\}.
\end{equation}
Constant shifts show that $0\le T_w(v)\le |w|$, where $|w|$ denotes the node's
width.

The virtual symbols are chosen outside the alphabets of both padded
strings. Thus every leaf value is an edit cost against a finite interval
of an extended target string, to which Lemma~\ref{lem:geometry} applies.

\begin{lemma}\label{lem:shift-tree}
At the root $o$,
\[
 d\le T_o(0),\qquad
 T_o(0)\le(1+2BD_0)d\quad\hbox{if }k\ge d.
\]
\end{lemma}
\begin{proof}
The recurrence minimizes the sum of leaf mismatches and twice the total
absolute shift difference along tree edges, with root shift zero.  For any
assignment, concatenate the shifted leaf target intervals.  By traversing
the tree in depth-first order, the sum of jumps between consecutive leaf
intervals, including the connections to the outer endpoints, is at most
twice the sum of edge shift differences.  The connection inequality from
Section~\ref{sec:geometry}, including its virtual-position version, therefore
bounds $d$ by the assignment's cost.  This proves the first assertion.

For the second, fix an optimal padded alignment and choose ordered points
$(j,b_j)$ at every source cut, with $b_0=0$ and $b_n=n$.  Assign shift $b_j-j$
to every node starting at $j$.  Its absolute value is at most $d$, because
only insertion and deletion steps change the shift.  These assignments are
allowed when $k\ge d$.

For each child, the shift difference from its parent is at most the cost of
the alignment subpath between their chosen starting points, and thus at most
the cost of the parent's subpath.  There are $B$ children per parent; the
parent subpaths at each depth partition the alignment.  Edge differences
therefore sum to at most $Bd$ at each of the $D_0$ depths.  A mismatching
width-one leaf has positive cost in its corresponding subpath: a zero-cost
subpath would be a matching diagonal.  Leaf mismatches sum to at most $d$,
and width-zero leaves contribute nothing.  The assignment has total cost at
most $(1+2BD_0)d$.
\end{proof}

\subsection{Pruning and precision sampling}

Nonuniform additive precision is the sampling principle developed by
Andoni, Krauthgamer and Onak~\cite[Lemma~3.12]{AndoniKrauthgamerOnak2010}
and refined in~\cite[Lemma~1.2]{AndoniKrauthgamerOnak2011}, with earlier
multiscale sampling antecedents in Indyk and
Woodruff~\cite{IndykWoodruff2005}. The reconstruction arguments of Andoni,
Krauthgamer and Onak already allow estimates to depend on the sampled
precisions. Here we use a finite threshold
distribution and prove an event covering all potential interval states,
together with the conditional cost of a first request.

Computing all of \eqref{eq:coarse-tree} would be too expensive. The guess
$k$ will also serve as an additive allowance at the root: on one event
of high probability, we will obtain an estimate $\widetilde T_o$ between $T_o/2-k$ and
$2T_o+k$ simultaneously for every entry and guess. Then
$2(\widetilde T_o(0)+k)$ is an upper bound on $d$ for every guess,
and the guess $d\le k<2d$ gives an $O(1+BD_0)$ approximation.
We can therefore replace a node by zero whenever its entire cost fits
within its additive allowance. Larger guesses permit more pruning;
their larger allowances are paid back in the returned estimate. Set
\[
 Q_0=H^4,\qquad \lambda=\frac1{64H},\qquad a_o=k.
\]
At a node with allowance $a_w$, independently for its children draw
$R_i$ uniformly from $\{1,\ldots,B\}$ and set
\begin{equation}\label{eq:coarse-threshold}
 t_i=\frac{a_wR_i}{BQ_0},\qquad a_{w_i}=\lambda t_i.
\end{equation}
All these random choices can be defined in advance, even below nodes that
will be pruned.  The implementation exposes only those it needs.

If $|w|\le a_w$, use the identically zero estimate $\widetilde T_w$.  At any
other leaf use its exact array.  At an unpruned internal node first compute
\[
 \widehat s_i(v)=\min_{v'\in[-k,k]\cap\Z}
       \{\widetilde T_{w_i}(v')+2|v-v'|\},
\]
and then put
\begin{equation}\label{eq:coarse-estimate}
 \widetilde T_w(v)=\sum_{i=1}^B
     \ind_{\widehat s_i(v)\ge t_i}
     \max\{\widehat s_i(v),a_w/Q_0\}.
\end{equation}
The descendants used to compute $\widehat s_i(v)$ depend on $t_i$, so
these child estimates cannot be treated as fixed in a concentration
bound. The proof below first compares their sampled contributions with
two lists formed from true child costs. It then concentrates those lists
without assuming that any child estimate is accurate.

\begin{lemma}\label{lem:coarse-precision}
Except on an event of probability less than $0.01$, simultaneously for all
initial entries, all guesses, all their nodes, and all shifts,
\begin{equation}\label{eq:coarse-accuracy}
 T_w(v)/f_w-a_w\le\widetilde T_w(v)\le f_wT_w(v)+a_w,
 \qquad
 f_w=\left(\frac{1+\lambda}{1-\lambda}\right)^{\operatorname{height}(w)}
 \le2.
\end{equation}
\end{lemma}
\begin{proof}
Fix an internal node and a shift, and write $s_i$ for the true child penalty minimum
in \eqref{eq:coarse-tree}. Let $f'$ be the factor in
\eqref{eq:coarse-accuracy} at its children's structural height. Both $s_i$
and $f'$ are independent of all thresholds. Suppose for the moment that
the child accuracy inequalities hold with this factor. Adding a nonnegative
penalty preserves the lower bound after division by $f'$ and the upper
bound after multiplication by $f'$.  Taking minima gives
\[
 s_i/f'-\lambda t_i\le\widehat s_i(v)\le f's_i+\lambda t_i.
\]
Let $u=a_w/Q_0$ and define
\[
 \phi_i(h)=\ind_{h\ge t_i}\max\{h,u\},\qquad
 h_i^- =\frac{s_i}{f'(1+\lambda)},\qquad
 h_i^+=\frac{f's_i}{1-\lambda}.
\]
If $h_i^-\ge t_i$, then
$\widehat s_i(v)\ge(1+\lambda)h_i^--\lambda t_i\ge h_i^-$.
If $\widehat s_i(v)\ge t_i$, then
$\widehat s_i(v)\le f's_i+\lambda\widehat s_i(v)$, and consequently
$\widehat s_i(v)\le h_i^+$.  These implications prove the pathwise sandwich
\begin{equation}\label{eq:threshold-sandwich}
 \phi_i(h_i^-)\le\phi_i(\widehat s_i(v))\le\phi_i(h_i^+).
\end{equation}

We now establish concentration independently of the supposition about child
accuracy.  Conditional only on ancestor thresholds, $u$ is fixed and
$t_i=uR_i/B$ are independent.  For either of the two fixed argument lists
$h_i=h_i^\pm$, if $0\le h_iz)
 \le2\exp\left(-\frac{z^2}{2uV+(2/3)uz}\right)
 \le2\exp(-\lambda Q_0/12).
\]
For the last inequality, if $V\ge a_w$, the denominator is at most $3uV$
and $z^2\ge\lambda a_wV$; if $V\le a_w$, the denominator is at most
$3ua_w$ and $z^2\ge a_w^2/4$.  Since $u\le a_w/2$, adding the bias yields
\begin{equation}\label{eq:threshold-concentration}
 |Z-V|\le\lambda V+a_w
\end{equation}
outside the indicated event.

These conditional bounds are uniform in the ancestor thresholds, so they
also hold unconditionally.  Take their intersection over both argument
lists and all fixed node and shift labels.  On that intersection, induction
from the leaves combines \eqref{eq:threshold-sandwich} and
\eqref{eq:threshold-concentration}.  The lower and upper bounds become
\[
 \frac{1-\lambda}{f'(1+\lambda)}T_w(v)-a_w
 \le\widetilde T_w(v)
 \le\frac{f'(1+\lambda)}{1-\lambda}T_w(v)+a_w,
\]
which is exactly the desired factor update.  A pruned node also satisfies
the inequalities because $T_w(v)\le |w|\le a_w$; exact leaves do so directly.
The factor satisfies $f_w\le\exp(2/63)<2$, since $D_0\le H$.

For completeness, the event count includes the entire domain, not merely
requested entries.  There are $O(M(N+1)^3)$ labeled main-tree states, $O(H)$
guesses per entry, $O(BN)$ nodes per coarse tree, and $O(N)$ shifts per guess.
The count of the two lists is therefore at most
\[
 CMBH(N+1)^5\le\exp(20H)
\]
for an absolute constant $C$ under the stated cutoff.  Here one may use
$B,M,H\le N$ in this regime and $\log_2(N+2)\le H$.  The union failure is at
most $2\exp(20H-H^3/768)<0.01$.  In particular, no conditioning on successful
descendants was used in the concentration calculation.
\end{proof}

\subsection{Converting the estimate to an integer seed}

For the padded entry, take the ceiling of
\begin{equation}\label{eq:initial-output}
 \min_k 2\bigl(\widetilde T_o(0)+k\bigr)
\end{equation}
and clamp it to $[0,N]$.  On the event of Lemma~\ref{lem:coarse-precision},
every candidate is at least $T_o(0)\ge d\ge c$.  A listed guess satisfies
$d\le k<2d$, and its rounded candidate is at most
\[
 4(1+2BD_0)d+4k+1
 \le (25+16BH)c
 \le BH^4c=A_{\mathrm{init}}c.
\]
Clamping preserves both bounds because $c\le N$.  Together with the direct
branches this proves the approximation assertion in Theorem~\ref{thm:seed}.

\subsection{The conditional cost of an adaptive request}

We next prove the cost assertion, including executions outside the accuracy
event.  For an array $E$ on $[-k,k]\cap\Z$, its penalty transform is computed
by a left sweep
\[
 L(v)=\min\{E(v),L(v-1)+2\}
\]
with the natural initial value, and the symmetric right sweep.  Their
pointwise minimum is
\[
 \min_{v'}\{E(v')+2|v-v'|\}.
\]
Both sweeps take $O(k)$ operations.  An identically zero child array, whose transform is also zero,
is represented by a marker without allocation.  At an unpruned internal
node the array work is $O(Bk)$, including visits and thresholds for all
children.  An unpruned leaf costs $O(k)$.  A pruned node needs only its width
test and marker.

Let $r$ be a node's depth in the coarse tree.  From
\eqref{eq:coarse-threshold}, along any fixed path,
\[
 a_w=\frac{k\prod R_e}{(64BH^5)^r},\qquad
 \E\left[\frac{a_{\mathrm{parent}}}{a_w}\,\middle|\,
          a_{\mathrm{parent}}\right]
 =64H^5\sum_{j=1}^B\frac1j\le H^8.
\]
It follows that $\E[k/a_w]\le H^{8r}$.  A node can incur array work only if
$|w|>a_w$, and pointwise
\[
 k\ind_{|w|>a_w}\le |w|\frac{k}{a_w}.
\]
Widths sum to $n$ at each depth.  Thus the expected array work for one guess,
including child overhead charged to expanded parents, is at most
\begin{equation}\label{eq:initial-array-work}
 O\bigl(1+Bn(D_0+1)H^{8D_0}\bigr).
\end{equation}
This estimate uses the random allowances alone and remains valid when the
estimated arrays are inaccurate.

All arithmetic and sampling can be performed with finite binary integers.
The quantities in \eqref{eq:coarse-threshold} are dyadic; a common denominator
for their descendants and the arrays needs
$O(D_0(p_*+5)\log H+\log H)$ bits.  Minima and maxima select existing dyadic
values, and sums preserve this common precision.  The same-shift candidate
in the penalty minimum gives
\[
 \widetilde T_w(v)\le\sum_i\widetilde T_{w_i}(v)+Ba_w/Q_0.
\]
Since $a_w\le k$ and there are $O(Bn)$ nodes, all estimate magnitudes are
bounded by $n+O(B^2nk)$.  Their bit lengths, and the cost of ordinary binary
arithmetic on them, fit the factor $H^{O(D_0+p_*+1)}$.  Each $R_i$ requires
exactly $\log_2B$ fair random bits.  Zero arrays are never materialized.

There are $O(H)$ guesses, and
\[
 D_0\le1+\frac{H}{p_*\log_2H},\qquad
 \log_2\bigl(H^{O(D_0+p_*+1)}\bigr)
 =O\left(\frac H{p_*}+(p_*+1)\log H\right)=o(H).
\]
Consequently \eqref{eq:initial-array-work}, including the arithmetic factors,
all guesses, equality tests, and padding, is $(1+|I|)2^{o(H)}$ in expectation.
Even a full coarse tree with all its shift arrays uses only polynomial
space: it has $O(Bn)$ nodes, $O(n)$ entries per array, and the bit lengths
just bounded.

Finally, assign a separate random stream to every initial entry, keyed by
its labeled main-tree node and endpoint pair, and cache the completed
answer.  Its calculation does not query other initial entries.  Before its
first request, none of the exposed computation can depend on its unused
stream: such a dependence would already have required evaluating this
entry.  Conditional on the entire preceding execution and the adaptive
request, the stream therefore has its original distribution.  The expected
cost bound applies conditionally exactly as stated; repeated requests use
the cached answer and pay only lookup work.  This deferred exposure realizes
the same full random table used in the simultaneous probability argument
and completes the proof of Theorem~\ref{thm:seed}.
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//03-seed.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//04-cones.tex ====
\section{A seed-to-refinement construction}\label{sec:cones}

The initial table has a large approximation factor.  We now describe one
refinement that reduces this factor while controlling expected excess over
the true cost.  Throughout the construction, fix the entire seed table;
randomness introduced by the refinement is independent of it.

\begin{theorem}[Refinement]\label{thm:refinement}
Use the parameters and interval tree of Section~\ref{sec:geometry} in the
large-input branch.  Let $A$ be a power of two with
$1\le A\le A_{\rm init}$, and let $U$ be an integer table on every labeled
tree node and every valid target state, with
\[
 0\le U(I,q)\le N,\qquad c(I,q)\le U(I,q)\le A c(I,q).
\]
Set $a=\max\{1,A/F\}$.  There is a randomized, finitely executable
refinement table $d_S$ such that, for every state $(I,q)$,
\begin{equation}\label{eq:refinement-guarantee}
 d_S(I,q)\ge c(I,q)/a,\qquad
 \E\bigl[\pos{d_S(I,q)-c(I,q)}\bigr]\le c(I,q)/\ell.
\end{equation}
The first inequality holds for every outcome of the refinement randomness;
the expectation in the second is conditional on the fixed table $U$.
At zero-cost states the returned value is zero for every outcome.
\end{theorem}

We call a seed \emph{good} if its input bounds
$c(I,q)\le U(I,q)\le A c(I,q)$ hold simultaneously at every state.
This section and the next define the refinement table
and establish its elementary
invariants.  Sections~\ref{sec:comparison}--\ref{sec:accuracy} prove the
expected-error bound.  Sections~\ref{sec:numerics} and~\ref{sec:work} give
the numerical and evaluation algorithms, including their work on
inaccurate seed tables.  The distinction matters: the refinement can
underestimate true cost when $a>1$.

\subsection{Cost cones and their local evaluation}

The number $a$ is an integer power of two.  Define
\[
 \widetilde U(I,q)=\max\{\ceil{U(I,q)/a},\abs{z(I,q)}\}.
\]
Since $Fc(I,q)$ is an integer, rounding does not spoil the bounds
\begin{equation}\label{eq:scaled-seed}
 \max\{c(I,q)/a,\abs{z(I,q)}\}
 \le\widetilde U(I,q)\le Fc(I,q).
\end{equation}
These bounds do not give endpoint regularity: neighboring seed entries
can have quite different overestimates. We replace the scaled table by
a lower envelope of cones. The charge $L_0|q-r|_1$ for moving away from
a center $r$ preserves the lower bounds $c/a$ and $|z|$, while making
the envelope Lipschitz. To evaluate it with few seed queries, we retain
centers on grids at several cost scales. A grid at the scale of the true
cost will provide a nearby inexpensive center; its value will then
force every minimizing center to be nearby as well.

The scales $b$ are the powers of two from $1$ to the largest power of two
at most $N$.  At scale $b$, put $g_b=\max\{1,b/P\}$.  A grid state has
both coordinates in $g_b\Z\cap[0,|y|]$, in nondecreasing order.
The state $r_b(q)$ rounds both coordinates of $q$ down to this grid.
All these spacings are integers.  If $g_b=1$, rounding is exact;
otherwise
\begin{equation}\label{eq:grid-error}
 \abs{q-r_b(q)}_1<2b/P.
\end{equation}

At a nonleaf $I$, consider all cones
\[
 q\longmapsto \widetilde U(I,r)+L_0\abs{q-r}_1
\]
whose centers are grid states at some scale $b$ with
$b/2\le U(I,r)\le4Ab$.  Include also the cone at every state $r$ with
$U(I,r)=0$, whether or not it occurs on one of these grids.  Define
$w_0(I,q)$ to be their minimum.  At a leaf set $w_0(I,q)=c(I,q)$.
The exact leaf rule will be used for every later table as well.

\begin{lemma}[Initial cones]\label{lem:initial-cones}
For the fixed seed in Theorem~\ref{thm:refinement},
\begin{equation}\label{eq:initial-cones}
 \max\{c/a,|z|\}\le w_0\le2Fc,
 \qquad \Lip(w_0(I,\cdot))\le L_0.
\end{equation}
At a nonleaf, the following local rule computes this global minimum
exactly.  If $U(I,q)=0$, return zero.  Otherwise omit the zero cones,
enumerate scales
\begin{equation}\label{eq:initial-local-scales}
 U(I,q)/(16A^2)\le b\le4A U(I,q),
\end{equation}
and enumerate grid centers at sup distance at most $U(I,q)$ from $q$,
retaining the eligibility test $b/2\le U(I,r)\le4Ab$.
\end{lemma}

\begin{proof}
Each cone dominates $c(q)/a$ and $|z(q)|$ by
\eqref{eq:scaled-seed} and the endpoint Lipschitz bounds.  Each has
Lipschitz constant $L_0$, so their minimum does too.  Leaves satisfy
these claims directly.

If $c(I,q)=0$, the seed has $U(I,q)=0$, and its own cone gives zero.
For $c=c(I,q)>0$, choose $b\le c<2b$ and set $r=r_b(q)$,
$e=|q-r|_1$.  By~\eqref{eq:grid-error},
\[
 c(I,r)\ge b-2b/P\ge b/2,
 \qquad c(I,r)<2b+2b/P\le4b.
\]
Thus $r$ is an eligible center.  Its cone has value at most
\[
 Fc(I,r)+L_0e
 \le Fc+(F+L_0)e
 \le Fc+66Fb/P\le2Fc.
\]

Any minimizing cone at a positive-cost state consequently has center
distance at most $2Fc/L_0=c/16$.  Its center's true cost lies in
$[15c/16,17c/16]$.  A zero center cannot minimize, since its distance
would be at least $c$.  For a minimizing nonzero center, eligibility
therefore gives
\[
 b\ge \frac{U(I,r)}{4A}
   \ge\frac{15c}{64A}\ge\frac{U(I,q)}{16A^2},
 \qquad
 b\le2U(I,r)\le\frac{17Ac}{8}\le4AU(I,q).
\]
Its sup distance is at most $c/16\le U(I,q)$.  Thus the local list
contains a global minimizer, and every member of the local list belongs
to the global family.  The two minima agree.
\end{proof}

We use this local rule as the executable definition even when the seed
is inaccurate, returning $N$ if its nonzero branch has no candidate.
Its work remains finite without any seed guarantee.  Indeed, the scale
interval has ratio at most $64A^3$, and $U(I,q)/b\le16A^2$ there.
The local list therefore contains
$O((1+PA^2)^2(1+\log A))=H^{O(p_*+1)}$ raw seed queries.
The returned values are nonnegative integers of magnitude
$O((L_0+1)N)$.  Global cone identities and Lipschitz continuity are
asserted only for a seed satisfying Theorem~\ref{thm:refinement}.

\subsection{Wide actions and Bellman propagation}

The next operator combines child estimates into a parent estimate. We
first allow each child to choose its target independently, paying the
connection charge for gaps and overlaps. Its minimum over earlier child
tables will remain an available parent option throughout the refinement;
the more restricted choices will use current child tables. Extending
each action cost by an endpoint cone retains spatial
regularity. Repeated propagation will also supply the average cost table
used to predict child alignments.

Let a nonleaf $I=(l,u]$ have child cuts
$l=l_0\le l_1\le\cdots\le l_M=u$, so
$I_i=(l_{i-1},l_i]$.  A \emph{representative} is a pair $(b,r)$ with
$r$ a grid state at scale $b$ and
\begin{equation}\label{eq:representative}
 b/(4a)\le w_0(I,r)\le8Fb.
\end{equation}
Write $p_0=r^--l$.  The wide action set $\mathcal A_{b,r}$ consists of
lists $\alpha=(s_1,\ldots,s_M)$ of valid child grid states satisfying
\[
 |s_i^--l_{i-1}-p_0|\le10b,
 \qquad |s_i^+-l_i-p_0|\le10b.
\]
Consecutive target intervals need not meet.  Their discrepancy is paid
for by the connection charge $\conn_r(\alpha)$ defined in
Section~\ref{sec:geometry}.  For child tables $f$, put
\begin{align}
 V_r(\alpha;f)&=\conn_r(\alpha)+\sum_{i=1}^M f(I_i,s_i),
 \label{eq:action-cost}\\
 \mathcal B_I(f)(q)
 &=\min\left\{w_0(I,q),\;
 \min_{(b,r)}\left[L|q-r|_1+
        \min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;f)\right]\right\}.
 \label{eq:bellman}
\end{align}
Every minimum over an empty set is $+\infty$.

The operator $\mathcal B_I$ is monotone in its child tables and is
$L$-Lipschitz in $q$.  It also preserves the lower bound
$\max\{c/a,|z|\}$.  For the latter assertion, if each child satisfies
the lower bound, then
\[
 V_r(\alpha;f)
 \ge\frac{\conn_r(\alpha)+\sum_i c(I_i,s_i)}a
 \ge c(I,r)/a,
\]
while the net-change-of-shift inequality gives
$V_r(\alpha;f)\ge|z(I,r)|$.  Endpoint Lipschitz continuity extends
both bounds along the cone, and $w_0$ satisfies them too.

Define the warmup tables at nonleaves by
\begin{equation}\label{eq:warmup}
 w_j(I,q)=\mathcal B_I(w_{j-1})(q)\quad(1\le j\le T),
 \qquad
 m=\frac1T\sum_{j=0}^{T-1}w_j,\qquad d_0=w_T.
\end{equation}
Here the operator receives the indicated tables on children.  Because
$w_1\le w_0$ and the operator is monotone, the warmup is nonincreasing.
In particular,
\begin{equation}\label{eq:warmup-invariants}
 \max\{c/a,|z|\}\le d_0\le m\le w_0\le2Fc,
 \qquad \mathcal B_I(d_0)\le d_0.
\end{equation}
The last inequality follows by one further application of the same
monotonicity.  The tables $w_j$ and $m$ are $L$-Lipschitz.

The average $m$ is useful because shifting its iteration range by one
changes it by only the initial-to-final drop divided by $T$:
\[
 \frac1T\sum_{j=1}^T w_j
 =m-\frac{w_0-w_T}{T}.
\]
For any fixed representative and wide action, average the inequalities
$w_j(I,q)\le L|q-r|_1+V_r(\alpha;w_{j-1})$ and then minimize over
that action. The result is
\[
 m(I,q)-\frac{w_0(I,q)-w_T(I,q)}T
 \le L|q-r|_1+\min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;m).
\]
Thus parent and child cost proxies satisfy the Bellman comparison up to
a controlled averaging error. Section~\ref{sec:comparison} will sum this
error over a tree of comparison states.

\subsection{Local evaluation of later cones}

The Bellman minimum, and later minima containing selected action cones,
admit the same local evaluation rule.  This rule is also what bounds the
computation when a seed is wrong. We enumerate complete cells because
Section~\ref{sec:bands} will make one shared choice for every cell; that
choice must be independent of which query first requests the cell.

\begin{lemma}[Cone locality]\label{lem:cone-locality}
Fix a good seed as in Theorem~\ref{thm:refinement}.  Take a minimum of
$w_0(I,q)$ and any family of cones of slope $L$ with nonnegative base
costs at representatives $(b,r)$.  If $w_0(I,q)=0$, its value is zero.
Otherwise it suffices to enumerate scales
\begin{equation}\label{eq:local-scales}
 w_0(I,q)/(16F)\le b\le8a w_0(I,q)
\end{equation}
and the following whole cells at each scale.  Partition endpoint-pair
space into half-open cells of side $\theta b$ on each axis, with lower
boundaries at multiples of $\theta b$.  Enumerate the cells intersecting
the closed sup square of radius $w_0(I,q)$ about $q$, and all valid
grid representatives in these cells.
\end{lemma}

\begin{proof}
Write $w=w_0(I,q)>0$.  A competitive cone has value at most $w$ and
therefore $|q-r|_1\le w/L$.  Since $L_0/L=1/4$,
$3w/4\le w_0(I,r)\le5w/4$.  Representative eligibility yields
\[
 b\ge3w/(32F)>w/(16F),\qquad b\le5aw<8aw.
\]
The representative belongs to the enumerated square and hence to an
enumerated cell.  Conversely, enumerating a whole cell only adds cones
already in the global family.  This proves exactness.
\end{proof}

For arbitrary local $w_0$, the scale count in~\eqref{eq:local-scales}
is $O(1+\log(aF))$, polynomial in $\ell$.  There are
$O((1+F/\theta)^2)$ cells per scale and $O((1+P)^2)$ grid states per
cell.  Indeed $w_0(I,q)/b\le16F$, and
$\theta b/g_b\le P$.  Cells and grid points are generated by ranges
of integer indices, without scanning unrelated positions.  These count
bounds do not assume a correct seed.  Empty lists give the $w_0$ option.

We have now obtained nonincreasing propagated estimates and the cost
proxy $m$.  The next step uses $m$ to identify narrow sets of shared
child alignments.  Expensive searches over the wide actions will use
earlier tables; the narrow sets limit calls to current tables.
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//04-cones.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//05-bands.tex ====
\section{Predicted bands and the refined tables}\label{sec:bands}

Starting from the fixed seed and the table $d_0=w_T$, we now define
$d_1,\ldots,d_S$. The construction proceeds by node height: when defining
the value at a parent and index $t$, all child tables through index $t$
are already defined. This is a mathematical ordering, not a requirement
to evaluate those tables in full. The algorithm will request only the
entries needed by the choices below.

There are two ways to choose a current-index action. A shared sample
compares rounded actions at nearby representatives; extending the chosen
cost by a cone gives a spatially regular estimate. An online rule uses
earlier child values to choose an action with small expected accumulated cost
relative to every fixed action in a predicted band. The parent update
combines these two estimates. We first construct the band and its child
cost bounds, then specify the online rule and the shared samples.

\subsection{A band predicted from prefix costs}

At a representative $(b,r)$ of a nonleaf, define
\[
 Z=\min_{\alpha\in\mathcal A_{b,r}}V_r(\alpha;m).
\]
Skip the band computations at this representative unless $Z$ is finite
and strictly positive.  Otherwise set $\widehat v=z(I,r)/Z$, the net
shift per unit of predicted cost. If shift accumulated proportionally to
this cost along an alignment, a prefix of cost $C$ would end at shift
$p_0+\widehat v C$. We use this relation to predict the shift at each
child cut. We call $|\widehat v|\le1-\tau$ the
\emph{velocity test}, and skip unless it holds.

For an internal cut $1\le j64Fb$.
Choose a canonical band action in a fixed ordering and round its two
coordinates separately at child $i$ down to multiples of
$\max\{1,\theta h_i\}$.  Denote the resulting action by
$\beta(b,r)$. Different children may round a shared endpoint to different
positions, so $\beta$ can have gaps or overlaps. It is used as a wide
action with its connection charge, rather than as a band action.
Finally, skip unless it belongs to $\mathcal A_{b,r}$
and
\begin{equation}\label{eq:rounded-guard}
 |z(I_i,s_i(\beta))|\le2h_i\qquad(1\le i\le M).
\end{equation}
Representatives passing all these tests will be called unskipped.
These tests affect only the band and rounded-action computations;
they never remove an action or representative from
$\mathcal B_I$.

Under the fixed good seed, the last two guards on $\beta$ pass
whenever the $h_\Sigma$ test passes.  Indeed,
$\theta h_i\ge\theta b/M\ge b/P$.  All relevant quantities are
powers of two, so the rounded spacing is a multiple of $g_b$.
Rounding preserves the order of each child's two endpoints and the range
$[0,|y|]$. If its
spacing is one, its error is zero; otherwise each coordinate error is
less than $\theta h_i$.  Since $|z|\le w_0\le h_i$ before rounding,
\[
 |z(I_i,s_i(\beta))|\le h_i+2\theta h_i\le2h_i.
\]
The endpoint shift radius after rounding is at most
$6b+64F\theta b<10b$.  Section~\ref{sec:comparison} will prove the
earlier $h_\Sigma$ test on the needed comparison nodes.

\subsection{The finite-mixture interface for online choices}

The online rule uses child values at indices less than $t$ to select
one band action at time $t$. Its accumulated current-index cost will be
compared with that of each fixed band action in Section~\ref{sec:regret}.
We encode a mixture of actions by its child-state marginals, with weights
chosen to recover the unnormalized sum of child costs.

Fix one unskipped band $\mathcal C=\mathcal C_{b,r}$. Its coordinates
are pairs $(i,s)$, one for each child and each state appearing at that
child in a band action.  Let $d_{\mathcal C}$ be their number.  Map
each action $\alpha$ to the probability vector $\rho(\alpha)$ that
places mass $h_i/h_\Sigma$ at $(i,s_i(\alpha))$ for every child,
and zero at its other coordinates.  Let
$\mathcal Q=\operatorname{conv}\{\rho(\alpha):\alpha\in\mathcal C\}$.
Every vector in this convex hull has the same total mass $h_i/h_\Sigma$
on the coordinates of child $i$.

Define coordinate vectors
\begin{align*}
 \widehat g_j(i,s)&=-d_{j-1}(I_i,s)/h_i,\\
 \Delta_j(i,s)&=(d_{j-1}(I_i,s)-d_j(I_i,s))/h_i,\\
 u_j&=\widehat g_j+(1-2\kappa)\Delta_j.
\end{align*}
Here $\widehat g_j$ predicts the negative normalized current cost from
the preceding index, and $\Delta_j$ is the observed correction:
\[
 \widehat g_j(i,s)+\Delta_j(i,s)=-d_j(I_i,s)/h_i,
 \qquad
 -h_\Sigma\langle\widehat g_j,\rho(\alpha)\rangle
 =\sum_i d_{j-1}(I_i,s_i(\alpha)).
\]
The fixed mass $h_i/h_\Sigma$ in each child block cancels the
normalization by $h_i$. The objective below uses $\Delta_j$ only for
$j0.
 \end{cases}
\end{equation}
Leaves continue to use their exact values. At a positive $w_0$ state,
this update truncates $Y_t$ to the interval
$[\Pi_t/(1+\delta),\Pi_t]$: an inexpensive online action can improve
the value only within this interval. The upper endpoint retains the
Bellman comparison, while the lower endpoint transfers the spatial
regularity of $\Pi_t$ to $d_t$ up to a factor $1+\delta$.
For a fixed pass, these definitions are well founded by induction on
node height: current-index values are requested only at children, and
at a fixed node the remaining refinement values have earlier indices.
Section~\ref{sec:work} gives the complete lazy evaluation order across passes.

\subsection{Deterministic invariants}

\begin{lemma}\label{lem:refinement-invariants}
For a seed satisfying Theorem~\ref{thm:refinement}, every outcome of
the refinement obeys
\begin{align}
 \max\{c/a,|z|\}&\le d_t\le d_{t-1}\le w_0,
 \label{eq:refinement-invariants}\\
 d_t(I,q)&\le(1+\delta)d_t(I,q')+L|q-q'|_1.
 \label{eq:refinement-lipschitz}
\end{align}
At nonleaves one also has
\begin{equation}\label{eq:bellman-sandwich}
 \mathcal B_I(d_t)(q)\le d_t(I,q)
           \le\mathcal B_I(d_{t-1})(q).
\end{equation}
For $d_0$, the spatial bound holds with Lipschitz constant $L$ and
without the factor $1+\delta$.
\end{lemma}

\begin{proof}
Induct on node height, and at a fixed node on $t$.  Every extra
candidate in $\Pi_t$ is a current-value wide-action cone.  The Bellman
candidate uses earlier child values, which are at least the current
ones by induction.  Hence $\Pi_t\ge\mathcal B_I(d_t)$, whereas
$\Pi_t\le\mathcal B_I(d_{t-1})$.  Each online candidate is a
current-value wide-action cone too, so
$Y_t\ge\mathcal B_I(d_t)$, including the empty case.  Taking the
specified minimum and maximum in~\eqref{eq:refined-update} proves
\eqref{eq:bellman-sandwich}.  In particular, no lower bound is inferred
from $\Pi_t/(1+\delta)$ alone.

At $t=1$, \eqref{eq:warmup-invariants} now gives $d_1\le d_0$.
At later times the left inequality in~\eqref{eq:bellman-sandwich}
at time $t-1$ gives $d_t\le d_{t-1}$.  The lower bound follows from
Bellman preservation and the child induction.

The global cone interpretation makes $\Pi_t$ $L$-Lipschitz, whether
or not any group estimate is accurate.  Moreover
$\Pi_t/(1+\delta)\le d_t\le\Pi_t$.  Thus
\[
 d_t(I,q)\le\Pi_t(I,q)
 \le\Pi_t(I,q')+L|q-q'|_1
 \le(1+\delta)d_t(I,q')+L|q-q'|_1.
\]
If $w_0(I,q)=0$, the Bellman and $\Pi_t$ values are zero, and the
explicit zero branch agrees with these inequalities.  The assertions
for $d_0$ follow from the warmup.
\end{proof}

For execution on an arbitrary seed, the local construction still gives
nonnegative values at most its local $w_0$.  All representative lists
and skipped-band tests remain finite.  We use these unconditional
facts for work bounds, and do not extend the correctness invariants of
Lemma~\ref{lem:refinement-invariants} to inaccurate seeds.

\subsection{Accuracy of one group selection}

For a band action define
$x_t(\alpha)=\sum_i d_t(I_i,s_i(\alpha))$.
Two band actions differ by at most $4\theta b/M$ in each child's
endpoint-pair metric.  Rounding the canonical action adds at most
$2\theta h_i$, so
$|s_i(\alpha)-s_i(\beta)|_1\le6\theta h_i$.
Also $\conn_r(\beta)\le2\theta h_\Sigma$, because the unrounded
action has shared endpoints.  It follows that
\begin{equation}\label{eq:rounded-action}
 \begin{split}
 V_r(\beta;d_t)&\le(1+\delta)x_t(\alpha)
                    +(6L+2)\theta h_\Sigma,\\
 d_t(I_i,s_i(\beta))&\le2h_i.
 \end{split}
\end{equation}
The first inequality uses~\eqref{eq:refinement-lipschitz}.  For the
second, use $d_t\le w_0$ and the $L_0$-Lipschitz bound to obtain
$w_0(I_i,s_i(\beta))\le h_i+2L_0\theta h_i\le2h_i$.

\begin{lemma}[One-group accuracy]\label{lem:group-accuracy}
Under the seed hypothesis of Theorem~\ref{thm:refinement}, fix complete
child tables and one group at time $t$.  With conditional
probability at least $1-H^{-4}$, all action-cost estimates used to choose
its representative are within $\gamma b$ of their actual costs.
Consequently, for any specified unskipped member $(b,r)$ of this
group, on the same event, simultaneously for every valid parent state
$q$ and every $\alpha\in\mathcal C_{b,r}$,
\begin{equation}\label{eq:group-accuracy}
 \Pi_t(I,q)\le L|q-r|_1+(1+\delta)x_t(\alpha)+e_*b,
 \qquad e_*=2\gamma+512LF\theta\le\kappa\delta.
\end{equation}
Here the inequality uses the global cone minimum, equivalently its
local evaluation from Lemma~\ref{lem:cone-locality}.
\end{lemma}

\begin{proof}
Conditioning fixes the bands, the $h_i$, the rounded actions, and all
their child costs.  The parent's group samples remain independent of
these data.  For a fixed member and sampled scale $h$, normalize one
sample to
\[
 X=\frac Mb\ind_{h_i=h}\,d_t(I_i,s_i(\beta)),
\]
where $i$ is uniform in $\{1,\ldots,M\}$.  By
\eqref{eq:rounded-action},
\[
 0\le X\le2Mh/b,
 \qquad \E X\le2h_\Sigma/b\le128F,
 \qquad \operatorname{Var}(X)\le256FMh/b.
\]
When $k_h0$.  Stop a branch at
a leaf of the interval tree or at a state of cost zero.  At each remaining
node, write $c=c(I,q)>0$, choose the dyadic scale $b$ with $b\le c<2b$, and put
\[
 r=r_b(q),\qquad e=|q-r|_1\le 2b/P.
\]
Choose an optimal alignment for $(I,r)$ and points on this path at the child
cuts, in their path order.  Use its exact endpoints at the outside cuts.
For repeated cuts, repeated path points are permitted; alternatively a
vertical segment can be assigned to one of the intervening empty children.
Round the internal target anchors down to the grid at scale $b$.  The resulting
child states $q_1,\ldots,q_M$ remain ordered and share endpoints, with outside
endpoints exactly $r$.  Denote this action by $\alpha^*$, and continue the
construction at its child states.

Fix a deterministic order for all choices of optimal paths and cut points.
The entire comparison tree, including its stopping states, then depends only
on the input strings and its starting state.  In particular it is independent
of every group sample and online draw in the refinement.  This tree is used
only in the proof.

\begin{lemma}[Comparison costs]\label{lem:comparison-tree}
At each nonterminal of the comparison tree, $(b,r)$ is a representative,
$b$ satisfies the local scale restriction~\eqref{eq:local-scales}, and
$\alpha^*$ is a wide action whose endpoint shifts are within $6b$ of
$p_0=r^- -l$.  Writing $c_i=c(I_i,q_i)$, we have
\begin{equation}\label{eq:comparison-split}
 c(I,r)\le\sum_i c_i\le (1+4M/P)c,
 \qquad c\le Le+\sum_i c_i.
\end{equation}
Let $C_{\mathrm{term}}$ be the sum of terminal true costs.  Then
\begin{equation}\label{eq:comparison-totals}
 \begin{aligned}
 C_{\mathrm{term}}&\le(1+8MJ/P)D\le2D,\\
 \sum_{\mathrm{nonterminal}}c&\le2JD,
 &\sum_{\mathrm{nonterminal}}e&\le4JD/P.
 \end{aligned}
\end{equation}
The sum of true costs at any depth is at most $2D$, also if stopped costs are
carried unchanged to subsequent depths.  At every terminal, $m=c$ and every
refinement estimate equals $c$.
\end{lemma}

\begin{proof}
If the grid spacing is one, no rounding changes any endpoint.  Otherwise an
endpoint moves by less than $b/P$.  Thus
\[
 c-e\le c(I,r)\le c+e.
\]
The initial-cone bounds give
\[
 w_0(I,r)\ge c(I,r)/a\ge b/(4a),
 \qquad
 w_0(I,r)\le2F c(I,r)\le8Fb,
\]
so $(b,r)$ is a representative.  At $q$, the same bounds imply
$w_0(I,q)/(16F)\le b\le8a w_0(I,q)$, as required for
\eqref{eq:local-scales}.

Along an alignment, each change of shift is caused by an insertion or
deletion and is at most the cost of that part of the path.  Hence every
unrounded anchor shift differs from $p_0$ by at most $c(I,r)$.  Rounding adds
less than $b/P$, so the distance is at most
\[
 c+e+b/P<(2+3/P)b<6b.
\]
This proves the wide-action and radius assertions.

The exact subpath costs before rounding sum to $c(I,r)$.  Each internal anchor
affects the endpoints of two child problems.  Endpoint Lipschitz continuity
therefore gives
\[
 \sum_i c_i\le c(I,r)+2(M-1)b/P
 \le c+2Mb/P\le(1+4M/P)c.
\]
Concatenation gives the other inequality in the first part of
\eqref{eq:comparison-split}; it also gives
$c\le c(I,r)+e\le\sum_i c_i+Le$.
These arguments apply without change to repeated cuts and empty child
intervals.

At each successive frontier of the tree, carry terminal costs unchanged.
The frontier sum grows by a factor at most $1+4M/P$ in one step.  The parameter
bounds give $4MJ/P\le1/2$, and consequently
\[
 (1+4M/P)^J\le1+8MJ/P\le2.
\]
This proves the terminal and level bounds.  There are at most $J$
nonterminal levels.  Summing $e\le2b/P\le2c/P$ proves the remaining bounds
in~\eqref{eq:comparison-totals}.

At a leaf, every table uses the exact answer.  At a zero-cost state, the
good seed is zero and the upper bound $w_0\le2Fc$ forces all warmup and
refinement values to be zero.  These are precisely the terminal cases.
\end{proof}

\subsection{Mass and energy telescopes}

If the warmup masses added exactly from children to parent, the energies
$z^2/m$ would telescope up to endpoint-rounding errors.  The masses do not
add exactly: a parent's mass can be either
larger or smaller than its children's total.  The warmup inequalities bound
the total upward discrepancy, and conservation of mass over the comparison
tree then bounds the total downward discrepancy as well.  This is why the
energy argument can use cost estimates instead of exact additive weights.

At a nonterminal use the representative and child states just constructed,
and define
\[
 m_q=m(I,q),\qquad m_i=m(I_i,q_i),\qquad W=\sum_i m_i,
 \qquad G=W-Z,\qquad R=m_q-W.
\]
Here $Z$ is the minimum wide-action cost with child table $m$, as in
Section~\ref{sec:bands}.  The comparison action has zero connection cost,
so $W\ge Z$.  The lower invariants and the comparison costs imply
\begin{equation}\label{eq:comparison-masses}
 0<\max\{c(I,r)/a,|z(I,r)|\}\le Z\le W\le4Fc<8Fb.
\end{equation}
In particular, the denominator $Z$ defining $\widehat v$ is positive at
every nonterminal comparison representative.

Write $z_i=z(I_i,q_i)$ and $z_r=z(I,r)$.  Since the child targets share
endpoints, $\sum_i z_i=z_r$.  Define the curvature quantity
\begin{equation}\label{eq:curvature-definition}
 K=\sum_i\frac{z_i^2}{m_i}-\frac{z_r^2}{W},
\end{equation}
with $0/0=0$.  A zero $m_i$ necessarily has $z_i=0$ by the lower invariant.
For $v=z_r/W$, the weighted variance identity is
\begin{equation}\label{eq:weighted-variance}
 K=\sum_{i:m_i>0}\frac{(z_i-vm_i)^2}{m_i}\ge0.
\end{equation}
These weights are costs supplied by the warmup; they are not interval
lengths.

\begin{lemma}[Total curvature]\label{lem:curvature-telescope}
On the fixed comparison tree, put $h=Le+w_0(I,q)/T$ at each nonterminal.
Then
\begin{equation}\label{eq:curvature-structural}
 \sum_{\mathrm{nonterminal}}(K+G)
 \le4C_{\mathrm{term}}+3\sum_{\mathrm{nonterminal}}e
                       +4\sum_{\mathrm{nonterminal}}h.
\end{equation}
Consequently,
\begin{equation}\label{eq:curvature-total}
 \sum_{\mathrm{nonterminal}}(K+G)
 \le5000F(1+J/P+J/T)D.
\end{equation}
\end{lemma}

\begin{proof}
First compare the parent and child warmup averages.  For each wide action,
average the parent warmup inequalities over indices $1,\ldots,T$, using
child indices $0,\ldots,T-1$.  Minimize the resulting action cost.  This gives
\[
 m_q-\frac{w_0(I,q)-w_T(I,q)}T\le Le+Z.
\]
Thus
\begin{equation}\label{eq:warmup-mass-slack}
 R+G\le h,\qquad R_+\le h,\qquad G\le R_-+h,
 \qquad R_\pm=\max\{\pm R,0\}.
\end{equation}
The masses cancel exactly across the tree:
\[
 \sum R=m_{\mathrm{root}}-C_{\mathrm{term}},
 \qquad
 \sum R_-\le\sum R_++C_{\mathrm{term}}
             \le\sum h+C_{\mathrm{term}}.
\]
In particular, summing $G\le R_-+h$ gives
$\sum G\le C_{\mathrm{term}}+2\sum h$.

Next define the energy of any comparison state by
\[
 E(I,q)=z(I,q)^2/m(I,q),
\]
again using $0/0=0$.  At a nonterminal put $z_q=z(I,q)$.  We have
$|z_q|\le m_q$, $|z_r-z_q|\le e$, and $|z_r|\le W$.  Moreover,
\[
 e\le2c/P\le2a m_q/P\le m_q,
\]
because $a\le A_{\rm init}$ and $2A_{\rm init}bH^{-1/4}$ or $G>bH^{-1/4}$; otherwise
call it \emph{non-bad}.  These are conditions on the deterministic comparison
tree and its warmup values.

\begin{corollary}\label{cor:bad-node-cost}
The total true cost of bad nodes satisfies
\begin{equation}\label{eq:bad-node-cost}
 \sum_{\mathrm{bad}}c
 \le10000FH^{1/4}(1+J/P+J/T)D.
\end{equation}
\end{corollary}

\begin{proof}
At a bad node, $c<2b<2H^{1/4}(K+G)$.  Sum and apply
Lemma~\ref{lem:curvature-telescope}.
\end{proof}

\subsection{Coverage by the computed bands}

The preceding estimate controls the cost of exceptional nodes.  We now show
that at every remaining node which passes the velocity test, the band and
rounding guards retain the comparison action.  This is the point where
cost-weighted curvature produces a usable prediction for the algorithm.

\begin{lemma}[Comparison-band coverage]\label{lem:comparison-band}
At a non-bad comparison node with $|\widehat v|\le1-\tau$, the action
$\alpha^*$ belongs to $\mathcal C_{b,r}$.  Its representative is not skipped:
the band is nonempty, $h_\Sigma\le64Fb$, and the rounded action $\beta(b,r)$
passes both the wide-action and imbalance guards.
\end{lemma}

\begin{proof}
Let $p_j^*$ be the comparison shift at internal cut $j$, and write
$M_j=\sum_{i\le j}m_i$.  The comparison prefix is feasible for
$\Phi_j(p_j^*)$, so this prefix cost is at most $M_j$.  Conversely, concatenate
any feasible prefix in that minimum with the comparison suffix.  The prefix's
final jump is exactly its connection to the suffix.  The resulting wide
action has cost at least $Z$, and hence
\[
 M_j-G\le\Phi_j(p_j^*)\le M_j.
\]
With $v=z_r/W$, we also have
\[
 |v-\widehat v|W=|z_r|G/Z\le G.
\]
Weighted Cauchy--Schwarz in~\eqref{eq:weighted-variance} gives
\[
 \sum_i|z_i-vm_i|\le\sqrt{KW}.
\]
The shared endpoints imply $p_j^*-p_0=\sum_{i\le j}z_i$.  Combining the last
three observations yields
\begin{equation}\label{eq:band-coverage}
 |p_j^*-p_0-\widehat v\Phi_j(p_j^*)|
 \le\sqrt{KW}+2G\le\tau\theta b/M.
\end{equation}
For completeness, the last numerical inequality follows from
$K,G\le bH^{-1/4}$, $W<8Fb$, and the parameter bounds:
\[
 \frac M b(\sqrt{KW}+2G)
 \le\sqrt{8\ell}\,H^{-3/40}+2H^{-1/5}
 \le\ell^{-44}=\tau\theta.
\]
Indeed $\ell^{200}\le H^{1/100}$ bounds the middle expression by
$\sqrt{8\ell}\,\ell^{-1500}+2\ell^{-4000}$.
The radius and shared-endpoint conditions were proved in
Lemma~\ref{lem:comparison-tree}.  Thus~\eqref{eq:band-coverage} proves
$\alpha^*\in\mathcal C_{b,r}$.

The diameter bound for the band implies that any of its child states is
within $4\theta b/M$ of $q_i$ in endpoint metric.  Using the
$L_0$-Lipschitz property of $w_0$ and the factor of at most two from dyadic
ceiling, we get
\[
 \begin{aligned}
 h_\Sigma
 &\le2b+2\sum_i w_0(I_i,q_i)+8L_0\theta b\\
 &\le2b+4F\sum_i c_i+8L_0\theta b
 \le64Fb.
 \end{aligned}
\]
The last step uses~\eqref{eq:comparison-split}, $c<2b$, and the parameter
range.  This verifies the sum guard.

Under the fixed good seed, the rounding verification following
\eqref{eq:rounded-guard} applies as soon as this sum guard holds.
It shows that $\beta(b,r)$ is a wide action and satisfies the imbalance
guard.  Rounding preserves the order of each child's two endpoints;
different child spacings may separate shared endpoints, with total
connection charge at most $2\theta h_\Sigma$.  Thus every guard passes.
\end{proof}
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//06-comparison.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//07-regret.tex ====
\section{Conditional regret and the first crossing}\label{sec:regret}

Fix a seed table satisfying the hypothesis of Theorem~\ref{thm:refinement},
and fix the comparison tree from Section~\ref{sec:comparison}.
We will bound the error accumulated at its nodes over the refinement indices.
The estimates may lie below true cost when $a>1$. To keep such
underestimation from cancelling an error elsewhere, define, for the analysis
only,
\[
 \overline d_t(I,q)=\max\{c(I,q),d_t(I,q)\}.
\]
At a nonterminal comparison node use the notation
$c,b,r,e,q_i,m_i,W,G,K$ of Section~\ref{sec:comparison}, and set
\begin{equation}\label{eq:node-regret-definition}
 \mathcal R_t(I,q)
 =\overline d_t(I,q)-Le-\sum_i\overline d_t(I_i,q_i).
\end{equation}
These quantities telescope over the fixed comparison tree. We first bound
their sum in time at an arbitrary node, then improve that bound on a node
whose comparison action belongs to a computed band.

\subsection{A telescoping bound at every comparison node}

\begin{lemma}\label{lem:generic-regret}
At every nonterminal comparison node,
\begin{equation}\label{eq:generic-regret}
 \sum_{t=1}^S\mathcal R_t
 \le \sum_i\bigl(\overline d_0-\overline d_S\bigr)(I_i,q_i)
 \le \sum_i(m_i-|z_i|)
 \le W-|z(I,r)|,
\end{equation}
where $z_i=z(I_i,q_i)$. In particular, the bound is at most $4Fc$.
If the node is not bad and $|\widehat v|>1-\tau$, it is at most
$(H^{-1/4}+4\tau F)c$.
\end{lemma}

\begin{proof}
The Bellman option and the comparison action give
\[
 d_t(I,q)\le Le+\sum_i d_{t-1}(I_i,q_i).
\]
The right side with all child values replaced by their clipped values is
at least $c$, by Equation~\ref{eq:comparison-split}. It therefore also bounds
$\overline d_t(I,q)$. Subtracting the same expression at index $t$ and
summing proves the first inequality in Equation~\ref{eq:generic-regret}.

For the second inequality, consider a child separately. If $d_0\le c_i$,
monotonicity makes both clipped endpoint values equal to $c_i$, so their
difference is zero, while $m_i\ge |z_i|$. If $d_0>c_i$, then
$\overline d_0=d_0\le m_i$ and $\overline d_S\ge |z_i|$. This proves the
required difference bound in both cases; it does not require
$\overline d_0\le m_i$ in the first case. Finally,
$\sum_i|z_i|\ge|z(I,r)|$ and $W\le4Fc$.

For the last assertion, $|\widehat v|=|z(I,r)|/Z>1-\tau$ implies
\[
 W-|z(I,r)|\le G+\tau W
 \le (H^{-1/4}+4\tau F)c,
\]
using $G\le bH^{-1/4}$ and $b\le c$ at a node that is not bad.
\end{proof}

\subsection{An entropy inequality with fixed block masses}

Exponential weighting and its potential analysis have a classical role in
online learning; see Freund and Schapire~\cite{FreundSchapire1997}.
Our predicted objective has the form of optimistic regularized leader,
as studied by Rakhlin and Sridharan~\cite[Section~2]{RakhlinSridharan2013}.
For our action vectors, each child receives a fixed total probability mass.
Cost decrements may differ greatly between children, but their variation
within a child is small.  The following deterministic lemma isolates the
reason that this weaker variation bound suffices.

\begin{lemma}[Monotone costs with fixed block masses]\label{lem:entropy}
Let $\mathcal Q$ be a nonempty compact convex set of probability vectors
in $\mathbb R^d$, containing a vector with every coordinate positive.
Partition the coordinates into blocks, and suppose that the total mass
in each block is the same for every vector in $\mathcal Q$.
For an integer $S\ge1$, let $f_0,\ldots,f_S\in[0,1]^d$ be
coordinatewise nonincreasing.
For $\eta>0$ and $0<\kappa<1/2$, set
\[
 \widehat g_t=-f_{t-1},\qquad
 \Delta_t=f_{t-1}-f_t,\qquad
 u_t=\widehat g_t+(1-2\kappa)\Delta_t.
\]
Suppose that the range of $\Delta_t$ within each block is at most
$\kappa/\eta$ for every $1\le t\le S$.  Let $\rho_t$ maximize
\[
 \mathcal H(\rho)+
 \eta\left\langle\sum_{j(1+\delta)A_t(\alpha_t),
 \qquad d_t(I,q)=\frac{\Pi_t(q)}{1+\delta}.
\]
The earlier-index Bellman option also gives
$\Pi_t(q)\le Le+x_{t-1}(\alpha_t)$, so, writing
$\Delta x=x_{t-1}(\alpha_t)-x_t(\alpha_t)$,
\[
 \Delta x>\delta A_t(\alpha_t)\ge\delta c\ge\delta b.
\]
On $E_t^c$, Equation~\ref{eq:group-accuracy} and $e_*\le\kappa\delta$
now give the full excess calculation
\[
 \begin{split}
 d_t(I,q)-A_t(\alpha_t)
 &\le\frac{e_*b-\delta Le}{1+\delta}
 \le\frac{e_*b}{1+\delta}\\
 &\le\frac{\kappa\delta b}{1+\delta}
 \le\kappa\Delta x.
 \end{split}
\]
On $E_t$, the added term $2Fc$ suffices because
$\overline d_t(I,q)\le2Fc$. This proves
Equation~\ref{eq:prefix-clipping} without requiring independence
between the sampled action and the group event.

If $t_\times\le S$, choose an action attaining the crossing.
On $E_{t_\times}^c$, its group bound gives
\[
 \Pi_{t_\times}(q)
 \le Le+(1+\delta)x_{t_\times}(\alpha)+e_*b
 0$ and its comparison tree from
Section~\ref{sec:comparison}. For brevity write
$\overline d_t=\max(c,d_t)$ at every state, as in
Section~\ref{sec:regret}.  Terminal values are exact, so summing
\eqref{eq:node-regret-definition} over the tree at a fixed index gives
the identity
\[
 \overline d_t(\mathrm{root})
 =C_{\mathrm{term}}+L\sum_{\mathrm{nonterminal}}e
                      +\sum_{\mathrm{nonterminal}}\mathcal R_t.
\]
Average this identity over $t=1,\ldots,S$.  Since the root estimates
decrease with $t$, the final positive error satisfies the deterministic
bound
\begin{equation}\label{eq:root-regret-telescope}
 (d_S(\mathrm{root})-D)_+
 \le C_{\mathrm{term}}-D+L\sum_{\mathrm{nonterminal}}e
       +\frac1S\sum_{\mathrm{nonterminal}}\sum_{t=1}^S\mathcal R_t.
\end{equation}
Lemma~\ref{lem:comparison-tree} bounds the first two terms by
$(8MJ/P+4LJ/P)D$.  We bound the last sum using the three classes
of comparison nodes.

On bad nodes use Lemma~\ref{lem:generic-regret} and $W\le4Fc$.
Corollary~\ref{cor:bad-node-cost} bounds their total contribution by
\[
 40000F^2 H^{1/4}(1+J/P+J/T)D.
\]
On nodes that are not bad but satisfy $|\widehat v|>1-\tau$, the same
lemma gives $(H^{-1/4}+4\tau F)c$. Every other nonterminal satisfies
Lemma~\ref{lem:comparison-band}, so Proposition~\ref{prop:node-regret}
applies. Its dimension and mass bounds are
\[
 \ln d_{\mathcal C}\le4(p_*+21)\ell,\qquad h_\Sigma\le64Fb\le64Fc.
\]
The cost sum over all nonterminal levels is at most $2JD$.

The conditional estimate at a node is valid after fixing its complete
child tables. Taking expectations and then summing uses only the tower
property and linearity of expectation. Independence between comparison
nodes, or simultaneous success of their group samples, is unnecessary.
Combining these bounds, the expected excess at the starting state divided
by $D$ is at most
\begin{align}
 \mathcal E={}&(8M+512F)J/P
 +40000F^2H^{1/4}(1+J/P+J/T)/S \notag\\
 &+\frac{2J}{S}\left[
 H^{-1/4}+4\tau F
 +64F\left(\frac{4(p_*+21)\ell}{\eta}+2\kappa\right)
 +2\delta\right]
 +132FJH^{-3}.\label{eq:total-error}
\end{align}
Here the last term includes both numerical-mixture loss and group-failure
loss: they are at most $128FJH^{-3}$ and $4FJH^{-4}$, respectively.

We verify the numerical bound explicitly. Substituting
$J\le100H/\ell$, $T\ge H^{3/4}$, $S=H/\ell^2$, $F=\ell$,
$M\le H^{1/20}$ and $P\ge H^{20}$ yields
\begin{align*}
 \mathcal E\le{}&52000H^{-18}
 +8.04\cdot10^6\ell^4H^{-1/2}
 +200\ell H^{-1/4}\\
 &+\frac{10^6(p_*+21)}{\ell^2}+13200H^{-2}.
\end{align*}
For the fourth term we have included
$[26400+51200(p_*+21)]/\ell^2+400/\ell^9$ from the bracket in
\eqref{eq:total-error}. Each of the five displayed terms is at most
$1/(8\ell)$ at $\ell\ge2^{1000}$ and $H\ge2^{\ell/2}$.
For example, the second requires only
\[
 \log_2(8\cdot8.04\cdot10^6)+5\log_2\ell\le\ell/4;
\]
it holds at the cutoff and remains true thereafter. The other
negative-power terms require weaker inequalities of the same form.
For the fourth, use $p_*+21\le\sqrt\ell$ and
$\sqrt\ell\ge2^{500}>8\cdot10^6$.
Consequently $\mathcal E<1/\ell$.

Since $\overline d_S-D=(d_S-D)_+$, this is the required expected
positive-excess bound. The deterministic lower bound is the invariant
from Section~\ref{sec:bands}. When $D=0$, that invariant and
$w_0\le2Fc$ give $d_S=0$ directly, without dividing by $D$.
The numerical construction in Section~\ref{sec:numerics} supplies the
mixtures used in this proof, and Section~\ref{sec:work} verifies finite
execution of every defined operation.
\end{proof}

\subsection{Improving simultaneous seeds}
The initial table of Theorem~\ref{thm:seed} has factor $A_{\rm init}$.
The algorithm maintains a power-of-two factor $A$ and an integer seed
$U\in[0,N]$ on the full state domain. A seed is called \emph{good} when
$c\le U\le Ac$ at every state. This is a mathematical event, not a test
performed by the algorithm.

While $A>F$, set $a=A/F$ and use $H^2$ independent copies of the
refinement, conditional on the previous complete table. For each state,
form the $H^2$ integers $\lceil a d_S\rceil$, take their upper middle
order statistic, and clamp the result to $[0,N]$. This defines the next
seed. Update
\begin{equation}\label{eq:seed-factor-update}
 A\longleftarrow4a.
\end{equation}
All copies share the preceding table, but use independent new streams.
Entries of each copy and of the new seed are stored on demand; their
coherent full-table interpretation is justified in Section~\ref{sec:work}.

\begin{lemma}\label{lem:seed-amplification}
Conditional on any fixed good preceding seed, the next seed is good for
factor $4a$ except with probability at most $\exp(10H-H^2)$.
\end{lemma}
\begin{proof}
At a fixed state of positive integer cost $c$, the refinement theorem and
Markov's inequality give
\[
 \Pr[d_S>2c]\le1/\ell.
\]
Every copy has $\lceil a d_S\rceil\ge c$. A copy with $d_S\le2c$ has
$\lceil a d_S\rceil\le2ac$, because $a$ and $c$ are integers. If strictly
more than half the copies have this upper bound, their upper middle order
statistic does too, hence in particular is at most $4ac$. The probability
that at least half fail is at most
\[
 2^{H^2}\ell^{-H^2/2}\le e^{-H^2}.
\]
Clamping cannot spoil the lower bound $c\le N$ or the upper bound.
At zero-cost states every copy is zero under the good seed.

There are at most $2M\max(1,|x|)$ labeled nodes and at most
$(|y|+1)^2$ valid states per node. Their product is less than $e^{10H}$
in the large branch. Union over this full domain proves the assertion.
No independence between different states is used.
\end{proof}

The update preserves powers of two and strictly decreases $A$, since
$F>4$. Writing $s_{\rm pass}$ for the number of median passes plus the
single final pass below, we have
\begin{equation}\label{eq:pass-count}
 s_{\rm pass}
 =O\left(\frac{(p_*+1)\ell}{\log_2\ell}\right)(1+\varepsilon)D\mid U\text{ fixed and good}]
 \le\frac{1}{\ell\varepsilon}\le\frac1{10}.
\]
Together with~\eqref{eq:seed-total-failure}, the unconditional failure
probability is less than $1/5$, and thus less than $1/3$. The lower bound
is not asserted on executions with a bad seed.

Clamping preserves the lower bound because $D\le N$. Rounding down also
preserves it because $D$ is an integer. Neither operation worsens the
upper bound. The initial equality test returns zero deterministically
when $D=0$, and the exact branches of Section~\ref{sec:geometry} are also
correct. This establishes the accuracy assertion of
Theorem~\ref{thm:main} on every input. It remains to prove that the
finite computations just specified, with all randomness and arithmetic
charged, have the claimed expected running time.
==== END An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//08-accuracy.tex ====

==== BEGIN An-Almost-Linear-Approximation-Scheme-for-Edit-Distance//09-numerics.tex ====
\section{Finite optimization and exact sampling}
\label{sec:numerics}

The optimization step is a finite implementation of the conditional-gradient
method of Frank and Wolfe~\cite{FrankWolfe1956}. We use the fixed-step
form analyzed by Jaggi~\cite[Algorithm~2 and Theorem~1]{Jaggi2013}, applied
to a smoothed entropy objective. Our linearization has a fixed error floor,
whose effect is included in the recurrence below. The rational arithmetic
and exact sampling are also part of the running-time analysis.

The online rule in Section~\ref{sec:bands} asks for a mixture of band
actions whose mean vector is close to an entropy maximizer.  Its finite
implementation separates recursive evaluation from numerical work.
First gather the earlier-index child values, once for each distinct
coordinate and history index occurring in the band.  The procedure below
then reuses this table while scoring the listed actions and constructing
a rational mixture.  It returns one exactly sampled action; only the
evaluation of that action requests current-index child values.  Thus the
mean vector is used to analyze the draw, whereas the returned refinement
value uses the cost of the single sampled action.

Fix an unskipped band $\mathcal C=\mathcal C_{b,r}$, and write
$d=d_{\mathcal C}$ for its number of coordinates.  Its vertices
$\rho(\alpha)$ are probability vectors, with child-block masses
$h_i/h_\Sigma$.  Let $v\in\mathbb Q^d$ be the coefficient vector
\[
 v=\eta\left(\sum_{j0$, so all
the prescribed block masses are positive, even on an execution with an
inaccurate seed.

\begin{lemma}[A finite entropy optimizer]
\label{lem:finite-optimizer}
Let $\mathcal Q$ be the convex hull of a nonempty finite list of rational
probability vectors in $\mathbb R^d$, and suppose that every coordinate
is positive in at least one listed vector.  Given a rational vector $v$
and an integer $H\ge4$, put $G_0=H+d+2$.  A rational algorithm constructs
a mixture of the listed vectors whose mean $\rho$ satisfies
\[
 \norm{\rho-\rho_t}_1\le H^{-3},
\]
where $\rho_t$ is the unique maximizer of
$\mathcal H(\rho)+\langle v,\rho\rangle$ on $\mathcal Q$.
The number of bit operations and the stored mixture size are polynomial
in $G_0$, the list size, and the maximum numerator or denominator bit
length of an input rational.
The mixture can be sampled exactly using fair random bits, with expected
cost polynomial in the same quantities and with a fixed space bound.
\end{lemma}

\begin{proof}
There is a feasible vector positive in every coordinate, obtained by
averaging the list.  The maximizer is positive as well: at a zero
coordinate, moving a small distance towards that average produces a
positive entropy contribution of order $s\ln(1/s)$, which dominates
the terms of order $s$ from the other coordinates and the linear
objective.  Strict concavity gives uniqueness.

Set $\sigma=G_0^{-50}$ and smooth the objective by replacing
$-x\ln x$ with $-(x+\sigma)\ln(x+\sigma)$ in each coordinate.  Denote
the result by $\mathcal F_\sigma$.  Integrating the derivative of
$x\ln x$, including at zero, gives
\begin{equation}
 \sup_{\rho\in\mathcal Q}
 \abs{\mathcal F_\sigma(\rho)-\mathcal F(\rho)}
 \le 4d\sqrt\sigma.
 \label{eq:entropy-smoothing}
\end{equation}
The gradient of $\mathcal F_\sigma$ has Euclidean Lipschitz constant
at most $1/\sigma$.  The diameter of $\mathcal Q$ is at most $2$.

Start at a listed vertex.  At step $j\ge0$, approximate every coordinate
of the gradient to absolute error at most $e_0=G_0^{-20}$.  Enumerate
the list and choose a vertex $v_j$ maximizing its scalar product with
this approximate gradient, resolving ties by a fixed order.  Update
\[
 \rho^{(j+1)}=(1-\xi_j)\rho^{(j)}+\xi_j v_j,
 \qquad \xi_j=\frac{2}{j+2}.
\]
Here $v_j$ denotes a selected vertex, whereas $v$ without a subscript
is the fixed linear coefficient vector.  The difference between two
probability vectors has $\ell_1$ norm at most $2$.  Consequently the
chosen vertex loses at most $2e_0$ in the true linearization, even
relative to a feasible mixture.  If $D_j$ is the gap from the maximum
of $\mathcal F_\sigma$, concavity and the gradient bound give
\begin{equation}
 D_{j+1}\le(1-\xi_j)D_j+2e_0\xi_j+
                  \frac{2\xi_j^2}{\sigma}.
 \label{eq:finite-optimizer-recursion}
\end{equation}
Since $\xi_0=1$, this estimate first gives
$D_1\le2e_0+2/\sigma$, independently of the size of the linear
coefficient vector.  Induction then gives
\[
 D_j\le2e_0+\frac{8}{\sigma(j+1)}\qquad(j\ge1).
\]
Run $K_{\mathrm{opt}}=G_0^{80}$ steps.  By
\eqref{eq:entropy-smoothing}, the resulting true objective gap is at
most
\[
 2G_0^{-20}+8G_0^{-30}+8dG_0^{-25}
 \le12G_0^{-20}.
\]

The Hessian of negative entropy is
$\operatorname{diag}(1/\rho_k)$, which dominates the identity on the
probability simplex.  The first-order inequality at the positive
maximizer, followed by this Hessian bound, therefore shows that its
objective gap at any feasible $\rho$ is at least
$\frac12\norm{\rho-\rho_t}_2^2$.  The statement at coordinates equal
to zero follows by continuity.  Hence
\[
 \norm{\rho-\rho_t}_1
 \le\sqrt d\,\norm{\rho-\rho_t}_2
 \le\sqrt{24d}\,G_0^{-10}\le H^{-3}.
\]

We next give an exact representation of every iterate.  After $K\ge1$
steps, the weight of the vertex selected at step $j$, where $0\le jM-1$.  Since $M\ge2$ in this branch,
$b/h<2Q_1$.  Evaluating the exact part for all children consequently
uses at most
\[
 C'M\theta^{-2}(1+2Q_1)
\]
distinct inputs as well.  This proves $M\ell^{O(1)}$ for one group
and one scale label, without an accuracy event.

There are $O(\log(FM))=O(\ell)$ scale labels.  The number of $b$
scales and cells requested by one query is polynomial in $\ell$,
as established above.  Once a winning rounded action is chosen,
evaluating its actual cost adds at most $M$ child calls per group.
Finally the online rule draws just one action for each applicable
$b$ scale; evaluating that actual action adds at most $M$ child
calls per scale.  These factors preserve the asserted bound.
\end{proof}

All other recursive inputs are earlier in the evaluation order.
Constructing $w_0$ uses a previous seed.  Computing bands, prefix
minima, and scale labels uses warmup data.  In $\Pi_t$ the wide
Bellman option uses $d_{t-1}$ on children.  The online coefficient
vector uses $d_j$ only for $j