betaFeedback

Reading v1View latest version

WorksComputer Science

Approximate Hamming Convolution via Rectangular Matrix Multiplication

Abstract

We study (1±ε)(1 \pm ε)-approximate text-to-pattern Hamming distance: given a length-NN pattern and a length-2N2N text, compute the Hamming distance at every alignment to relative error εε. For every fixed a≥0a \ge 0 and ε=N−aε= N^{-a}, we give a randomized algorithm with simultaneous high-probability correctness on a logarithmic-word RAM and expected running time O~(Nω(4a)/2)\widetilde{O}(N^{ω(4a)/2}), where O~\widetilde{O} suppresses subpolynomial factors and ω(k)ω(k) is the exponent for multiplying an n×nkn \times n^k matrix by an nk×nn^k \times n matrix. With a recent rectangular bound, this improves the published bounds [CGK+20, FKN26] for 1/12<a<(3+3)/161/12 < a < (3 + \sqrt{3})/16. In particular, the algorithm runs in expected time O~(N)\widetilde{O}(N) for 0≤a≤1/80 \le a \le 1/8, extending the previous near-linear guarantee through a=1/12a = 1/12.

Introduction and results

For equal-length strings X,YX,Y over an integer alphabet Σ\Sigma, their Hamming distance is

Ham⁡(X,Y)=∣{j:X[j]≠Y[j]}∣.\operatorname{Ham}(X,Y) = |\{j : X[j] \ne Y[j]\}|.

Given a text T∈ΣnT \in\Sigma^n and a pattern P∈ΣmP \in\Sigma^m, where m≤nm \le n, their text-to-pattern Hamming distance is the array

S[i]=Ham⁡(T[i:i+m],P),0≤i≤n−m.(1)S[i] = \operatorname{Ham}(T[i : i + m], P), \qquad0 \le i \le n - m. \tag*{(1)}

We use zero-based indices and half-open substrings. For 0<ε≤10 < \varepsilon\le1, a (1±ε)(1 \pm\varepsilon)-approximation is an array SεS_\varepsilon with (1−ε)S[i]≤Sε[i]≤(1+ε)S[i](1 - \varepsilon)S[i] \le S_\varepsilon[i] \le(1 + \varepsilon)S[i] for every ii.

By the standard blocking reduction, we may assume m=Nm = N and n=2Nn = 2N. We require simultaneous correctness at all alignments with high probability. The alphabet has size NO(1)N^{O(1)}, and symbols occupy O(log⁡N)O(\log N) bits. Reversing the pattern expresses the equality counts as convolution coefficients; this accounts for the term Hamming convolution.

We use a word RAM with Θ(log⁡N)\Theta(\log N)-bit words and include all preprocessing and output costs. Throughout, O~\widetilde{O} suppresses subpolynomial factors in the input length, including polylogarithmic factors. We write ε=N−a\varepsilon= N^{-a} for fixed a≥0a \ge0 when stating our running-time bounds. Our algorithm improves the published running-time bounds for 1/12<a<(3+3)/161/12 < a < (3 + \sqrt{3})/16.

Main result

Let ω(k)\omega(k) denote the arithmetic exponent for multiplying an n×⌈nk⌉n \times\lceil n^k\rceil matrix by a ⌈nk⌉×n\lceil n^k\rceil\times n matrix over the rationals. The shape parameter k≥0k \ge0 is fixed, and every fixed positive exponent slack is permitted. We use the same ω(k)\omega(k) for word-RAM multiplication of polynomially bounded integer matrices. Reading the matrices and writing their product are included; the size bound ω(k)≥max⁡{2,1+k}\omega(k) \ge\max\{2,1+k\} covers these costs.

Theorem 1.1. Fix a≥0a \ge0 and set ε=N−a\varepsilon= N^{-a}. For all sufficiently large NN, all distances in (1) admit simultaneous relative-ε\varepsilon estimates with probability at least 1−N−101-N^{-10} in expected time

O~(Nω(4a)/2).(2)\widetilde{O}\left(N^{\omega(4a)/2}\right). \tag*{(2)}

The sketch overhead is polylogarithmic independently of aa; constants may depend on aa and the alphabet bound.

The proof has three parts: a sketch for one distance, its batched construction for shifted strings, and an exact bounded-distance handoff. The last part uses a published algorithm at threshold ⌈N⌉\lceil\sqrt{N}\rceil.

Improvement range

For the numerical consequence, we use rectangular bound [7 Corollary 1.2]:

ω(k)≤{2,0≤k≤1/2,1+k+1/(4k),k≥1/2.(3)\omega(k) \le\begin{cases} 2, & 0 \le k \le1/2, \\ 1+k+1/(4k), & k \ge1/2. \end{cases} \tag*{(3)}

These arithmetic bounds hold over fields of characteristic zero, including the rationals. Substituting (3) into Theorem 1.1 gives, for 1/8≤a1/8 \le a, running time

O~(N1/2+2a+1/(32a)).\widetilde{O}\left(N^{1/2+2a+1/(32a)}\right).

For 0≤a≤1/80 \le a \le1/8, the same theorem gives running time O~(N)\widetilde{O}(N). The stated Corollary 9.2 of [2], with matrix dual exponent α≥1/2\alpha\ge1/2, guarantees near-linear time through a=1/12a=1/12. The new algorithm improves the cited published bounds throughout (1/12,(3+3)/16)(1/12,(3+\sqrt{3})/16). At the upper endpoint, it matches the bound in [4].

Previous work and the scope of the comparison

Chan, Golan, Kociumaka, Kopelowitz, and Porat [2] introduced structured modular sampling and the use of rectangular matrix products for approximate Hamming matching. Their algorithm already gives near-linear running time for sufficiently long patterns relative to the inverse accuracy. Their stated Corollary 9.2 gives near-linear time when m>ε−max⁡{4+4/α,10}m > \varepsilon^{-\max\{4+4/\alpha,10\}}. With the matrix dual-exponent bound α≥1/2\alpha\ge1/2, this guarantees O~(N)\widetilde{O}(N) time through a=1/12a=1/12. Our algorithm extends the guarantee to a=1/8a=1/8. The comparison uses their stated dependency with this matrix-bound substitution. Our construction retains the general idea of few shifts on each side and shared linear sketches. It replaces their fixed-scale sampler and decoder by sampling nodes at each depth in a binary addition identity. The second moment needs only a standard universal-hashing bound. For small distances, we use the deterministic exact algorithm of [5 Theorem 1] at k=⌈N⌉k=\lceil\sqrt{N}\rceil.

Abrahamson [1] gives the classical exact O~(N3/2)\widetilde{O}(N^{3/2}) algorithm. Chan, Jin, Vasilevska Williams, and Xu [CJWWX23] remove logarithmic factors, obtaining an O(N3/2)O(N^{3/2}) Las Vegas algorithm, and give a uniform approximation bound with inverse-accuracy exponent 8/(11−ω(1))8/(11-\omega(1)). Fischer, Kirkpatrick, and Nakos [4] give the stronger uniform bound O~(Nε−2/3)\widetilde{O}(N^{\varepsilon-2/3}). We use their approximation bound as a comparison benchmark.

To compare the approximation exponent with matrix multiplication, let h(a)h(a) be the infimum achievable running-time exponent for relative error ε=N−a\varepsilon=N^{-a}, with the computational model and simultaneous success guarantee of Theorem 1.1. Our result implies

h(a)≤ω(4a)2,a≥0.(4)h(a) \le\frac{\omega(4a)}{2}, \qquad a \ge0. \tag*{(4)}

The reduction in [5 Section 4, Corollary 13] further implies

h(a)≥ω(2a−1)2,12≤a≤1.(5)h(a) \ge\frac{\omega(2a-1)}{2}, \qquad\frac{1}{2} \le a \le1. \tag*{(5)}

Binary partitions of randomly permuted positions

Write [m]={0,…,m−1}[m]=\{0,\ldots,m-1\}. For M≥2M\ge2 set

d=⌈log⁡2M⌉,U=2d,pj=2j(0≤j≤d).(6)d=\lceil\log_2 M\rceil,\qquad U=2^d,\qquad p_j=2^j\quad(0\le j\le d). \tag*{(6)}

Choose a uniformly random odd μ∈[U]\mu\in[U] and let π(t)=μt mod U\pi(t)=\mu t\bmod U. Since μ\mu is odd, π\pi permutes [U][U]. For every power of two p≤Up\le U, partition the permuted positions into pp consecutive intervals:

Ip(r)=[rU/p,(r+1)U/p),Hp(t)=⌊pπ(t)/U⌋.(7)I_p(r)=\left[rU/p,(r+1)U/p\right),\qquad H_p(t)=\left\lfloor p\pi(t)/U\right\rfloor. \tag*{(7)}

Bucket rr at level pp has children 2r2r and 2r+12r+1 at level 2p2p. At the final level p=Up=U, every position has its own bucket.

This is the standard multiply-shift hash family. We include its collision bound for completeness; see also [6 Section 2.3, equations (9)–(10)].

Lemma 2.1 (Collision bound). For every fixed pair of distinct positions x,y∈[U]x,y\in[U] and every power of two p≤Up\le U,

Pr⁡μ[Hp(x)=Hp(y)]≤2/p.(8)\Pr_{\mu}[H_p(x)=H_p(y)]\le2/p. \tag*{(8)}

Proof. The case p=1p=1 is immediate. Write y−x=gzy-x=gz, where gg is a power of two and zz is odd. As μ\mu varies, the cyclic difference μ(y−x) mod U\mu(y-x)\bmod U is uniform over the U/(2g)U/(2g) odd multiples of gg. Put W=U/pW=U/p. A collision requires this difference to lie in [0,W)[0,W) or (U−W,U)(U-W,U). If W≤gW\le g, neither event is possible. Otherwise W/gW/g is an even integer, and each end interval contains W/(2g)W/(2g) eligible values. Their total probability is at most (W/g)/(U/(2g))=2/p(W/g)/(U/(2g))=2/p.

A sketch from binary addition

Fix strings A,B∈ΣMA,B\in\Sigma^M. Encode symbols injectively as vectors in F2w\mathbb{F}_2^w, where w=O(log⁡N)w=O(\log N), and put xt=A[t]⊕B[t]x_t=A[t]\oplus B[t]. Exactly D=Ham⁡(A,B)D=\operatorname{Ham}(A,B) of these vectors are nonzero. Extend the sequence by zeros to length UU, and arrange it at the leaves of the binary interval tree in permuted order. For a zero-padded string CC, write fC(p,r)f_C(p,r) for the XOR of its codes at positions tt with Hp(t)=rH_p(t)=r.

For bits yty_t at the leaves of any full binary tree, let qvq_v be the XOR of the bits below node vv. At each internal node, qv=qv0⊕qv1q_v=q_{v0}\oplus q_{v1}, so the identity x+y=(x⊕y)+2xyx+y=(x\oplus y)+2xy gives

qv0+qv1=qv+2qv0qv1.q_{v0}+q_{v1}=q_v+2q_{v0}q_{v1}.

Summing over internal nodes gives

∑tyt=qroot+2∑v internalqv0qv1.(9)\sum_t y_t = q_{\mathrm{root}} + 2\sum_{v\ \mathrm{internal}} q_{v0}q_{v1}. \tag*{(9)}

Write r(C)=⨁tC[t]r(C)=\bigoplus_t C[t] for the total XOR of a string and set

c(A,B)=1{r(A)≠r(B)}=2Ehh(⨁txt),(10)c(A,B)=1_{\{r(A)\ne r(B)\}}=2\mathbb{E}_h h\left(\bigoplus_t x_t\right), \tag*{(10)}

where h:F2w→F2h:\mathbb{F}_2^w\to\mathbb{F}_2 is a uniform linear functional. We compute this root contribution exactly.

Complementary labels and the estimator

For 0<η≤1/100<\eta\le1/10, take

K=⌈104η−2d⌉,L=Kd.(11)K=\left\lceil10^4\eta^{-2}d\right\rceil,\qquad L=Kd. \tag*{(11)}

At each internal depth j∈{0,…,d−1}j\in\{0,\ldots,d-1\}, draw KK samples. Each sample sets p=2jp=2^j, chooses a uniform parent r∈[p]r\in[p] and a fresh uniform linear functional hh, and assigns each string CC the label

λ(C)=(h(fC(2p,2r)),h(fC(2p,2r+1))).\lambda(C)=\left(h(f_C(2p,2r)),h(f_C(2p,2r+1))\right).

The multiplier μ\mu is shared; all masks and sampled parents are independent conditional on μ\mu.

Apply the same samples to any fixed families of row and column strings. For each sample, encode a row label by a four-dimensional one-hot vector weighted by 4p4p, and encode the bitwise complement of a column label by a Boolean one-hot vector. Concatenate the LL encodings into matrices V,WV,W of inner dimension 4L4L. Define each estimate directly by

XA,B=c(A,B)+1K(VW)A,B.(12)X_{A,B}=c(A,B)+\frac{1}{K}(VW)_{A,B}. \tag*{(12)}

Row entries are at most 2U2U, column entries are Boolean, and product entries are at most 2UL2UL.

Lemma 3.1 (Unbiasedness and accuracy). Fix a pair A,BA,B and write X=XA,BX=X_{A,B} and D=Ham⁡(A,B)D=\operatorname{Ham}(A,B). For every fixed multiplier μ\mu, E[X∣μ]=D\mathbb{E}[X\mid\mu]=D. For D≥1D\ge1,

E[(X−D)2]≤32d(D2)K,(13)\mathbb{E}[(X-D)^2]\le\frac{32d\binom{D}{2}}{K}, \tag*{(13)}

and Pr⁡[∣X−D∣>ηD]≤1/100\Pr[|X-D|>\eta D]\le1/100. If D≤1D\le1, then X=DX=D always.

Proof. For one sample at depth jj, put

b0=h(⨁t∈[U]H2p(t)=2rxt),b1=h(⨁t∈[U]H2p(t)=2r+1xt).b_0=h\left(\bigoplus_{\substack{t\in[U]\\H_{2p}(t)=2r}}x_t\right),\qquad b_1=h\left(\bigoplus_{\substack{t\in[U]\\H_{2p}(t)=2r+1}}x_t\right).

The row and column labels are complements exactly when b0=b1=1b_0=b_1=1. Its contribution to the product entry is therefore

Zj=4p b0b1,X=c(A,B)+1K∑j=0d−1∑ℓ=1KZj,ℓ.(14)Z_j=4p\,b_0b_1,\qquad X=c(A,B)+\frac{1}{K}\sum_{j=0}^{d-1}\sum_{\ell=1}^{K}Z_{j,\ell}. \tag*{(14)}

For a fixed mask hh, let qvq_v be the parity of the bits h(xt)h(x_t) below node vv. By (10) and the tree identity,

E[X∣μ]=2Eh[qroot+2∑v internalqv0qv1]=2∑tEhh(xt)=D.\mathbb{E}[X \mid\mu] = 2\mathbb{E}_h\left[q_{\mathrm{root}} + 2\sum_{v\ \mathrm{internal}} q_{v0}q_{v1}\right] = 2\sum_t \mathbb{E}_h h(x_t) = D.

Here every fixed nonzero word has hh-value one with probability 1/21/2.

A nonzero internal-node sample requires at least two mismatches in its sampled parent. A fixed pair shares a parent with probability at most 2/p2/p by Lemma 2.1, and that parent is sampled with probability 1/p1/p. A union bound gives

Pr⁡[b0b1=1]≤2(D2)p2,EZj2≤32(D2).\Pr[b_0b_1=1] \le\frac{2\binom{D}{2}}{p^2}, \qquad\mathbb{E}Z_j^2 \le32\binom{D}{2}.

These expectations include μ\mu, the parent, and hh. Conditional independence and the conditional mean DD therefore give

E[(X−D)2]=EμVar⁡(X∣μ)≤∑j=0d−1EZj2K≤32d(D2)K.\mathbb{E}[(X-D)^2] = \mathbb{E}_{\mu}\operatorname{Var}(X\mid\mu) \le\frac{\sum_{j=0}^{d-1}\mathbb{E}Z_j^2}{K} \le\frac{32d\binom{D}{2}}{K}.

Chebyshev and (11) give the stated failure probability. For D≤1D \le1, every two-child product is zero and c(A,B)=Dc(A,B)=D.

Repeat the entire construction, including the multiplier, R=O(log⁡N)R=O(\log N) times independently and take a median for each pair. For any O(N)O(N) fixed pairs with M=O(N)M=O(N), amplification and a union bound give simultaneous relative-η\eta accuracy with failure at most N−12N^{-12}. Pairs may share all the randomness. Counting both children, the total number of bit coordinates on either side is

O(RL)=O(η−2log⁡3N).(15)O(RL)=O(\eta^{-2}\log^3 N). \tag*{(15)}

Batching shifted strings by matrix multiplication

An exact padding offset

Fix an integer 1≤z≤N1\le z\le N and a new symbol ⊥∉Σ\perp\notin\Sigma. Append zz copies of a genuine symbol, for example P[0]P[0], to TT, obtaining T′T'. Define length-M=N+zM=N+z strings

Au=⊥uP⊥z−u(0≤u<z),Bs=T′[s:s+M](s∈{0,z,2z,…}, s≤N).(16)A_u=\perp^uP\perp^{z-u}\quad(0\le u<z),\qquad B_s=T'[s:s+M]\quad(s\in\{0,z,2z,\ldots\},\ s\le N). \tag*{(16)}

These strings are implicit. Each requested shift is uniquely i=s+ui=s+u with 0≤u<z0\le u<z. Only pairs with s+u≤Ns+u\le N are used.

Lemma 4.1 (Exact padding offset). Writing Eu,s=Ham⁡(Au,Bs)E_{u,s}=\operatorname{Ham}(A_u,B_s), every used pair satisfies

Eu,s=S[s+u]+z.(17)E_{u,s}=S[s+u]+z. \tag*{(17)}

Proof. At positions u,…,u+N−1u,\ldots,u+N-1, the comparisons are exactly those of alignment s+us+u. They lie in the original text because s+u≤Ns+u\le N. At the other zz positions, AuA_u contains ⊥\perp and BsB_s contains a genuine symbol, so every comparison is a mismatch. The appended symbols ensure all windows exist, including the final block.

Shifted buckets as interval-XOR queries

Encode ⊥\perp as zero and genuine symbols as distinct nonzero binary vectors. Fix a repetition’s multiplier μ\mu and U=O(N)U=O(N). Form the length-UU pattern array and maintain the moving text array

F[q]=⨁0≤j<NμjmodU=qP[j],(18)F[q]=\bigoplus_{\substack{0\le j<N\\ \mu j\bmod U=q}}P[j], \tag*{(18)}
Gs[q]=⨁s≤t<s+MμtmodU=qT′[t].(19)G_s[q]=\bigoplus_{\substack{s\le t<s+M\\ \mu t\bmod U=q}}T'[t]. \tag*{(19)}

For a circular interval II in [U][U], write F(I)F(I) and Gs(I)G_s(I) for the XORs of the array entries it contains. Prefix XORs of FF answer each such query in constant time, splitting a wrapping interval into at most two intervals. Constructing FF and its prefixes costs O(N+U)O(N+U). Maintain GsG_s in a binary tree storing the XOR of each dyadic interval. A point update changes one node per level, and a range query uses O(log⁡U)O(\log U) such intervals, so each operation takes O(log⁡U)O(\log U) time. Sweep increasing block starts ss, removing text positions that leave [s,s+M)[s,s+M) and inserting those that enter. There are O(N)O(N) updates over the entire sweep, costing O(Nlog⁡U)O(N\log U) including initialization. One tree serves every partition level.

The bucket XORs of the padded strings satisfy

fAu(p,r)=F(Ip(r)−μu),f_{A_u}(p,r)=F(I_p(r)-\mu u),
fBs(p,r)=Gs(Ip(r)+μs).(20)f_{B_s}(p,r)=G_s(I_p(r)+\mu s). \tag*{(20)}

Here interval translations are modulo UU. Indeed, the pattern symbol at position u+ju+j is mapped to μu+μj mod U\mu u+\mu j\bmod U, and the text symbol at relative position t−st-s is mapped to μt−μs mod U\mu t-\mu s\bmod U. Translated intervals retain their length, although their endpoints need not be aligned with the partition. The text array uses absolute text positions, reduced modulo UU. Emit each column’s coordinates while its window is current; the algorithm stores no separate tree for each column.

Evaluating the padded distances

Construct the labels in § 3 using (20). Since ⊥\perp is encoded as zero, r(Au)=r(P)r(A_u)=r(P) for every row. The exact root correction is therefore

cs=1{r(P)≠r(Bs)},c_s=\mathbf{1}_{\{r(P)\ne r(B_s)\}},

independent of uu. Compute all csc_s from the total XOR of PP and prefix XORs of T′T' in O(N)O(N) time. For each repetition, form V,WV,W and evaluate

Xu,s=cs+1K(VW)u,s.(21)X_{u,s}=c_s+\frac{1}{K}(VW)_{u,s}. \tag*{(21)}

Then take medians across repetitions.

Proposition 4.2 (Cost of the batched sketches). Fix a≥0a\ge0 and let η=Θ(N−a)≤1/10\eta=\Theta(N^{-a})\le1/10. For z=⌈N⌉z=\lceil\sqrt{N}\rceil, all padded distances in (16) can be estimated to relative error η\eta, simultaneously with failure probability at most N−12N^{-12}, in time

O~(Nω(4a)/2).(22)\widetilde{O}\left(N^{\omega(4a)/2}\right). \tag*{(22)}

Proof. There are zz rows and O(N/z)O(N/z) columns, hence O(N)O(N) pairs. Lemma 3.1 and median amplification apply to these fixed strings. All randomness may be shared between different pairs. Correctness uses a per-pair guarantee followed by a union bound.

Equation (15) bounds the total number of coordinates by O~(η−2)\widetilde{O}(\eta^{-2}). Process repetitions separately. Partition each product’s inner dimension into blocks of length ⌈η−2⌉\lceil\eta^{-2}\rceil and pad the final block. The total number of resulting matrix products is polylogarithmic. Each product has dimensions O(N1/2)×O(N2a)×O(N1/2)O(N^{1/2}) \times O(N^{2a}) \times O(N^{1/2}). Taking n=⌈N⌉n=\lceil\sqrt{N}\rceil, this costs O~(nω(4a))=O~(Nω(4a)/2)\widetilde{O}(n^{\omega(4a)})=\widetilde{O}(N^{\omega(4a)/2}) time. Every coordinate uses at most two interval queries and a parity mask per row or column. Pattern queries take constant time, and text queries take O(log⁡N)O(\log N) time. By (15), the total feature construction cost, apart from preprocessing, is

O~((z+N/z)η−2),\widetilde{O}\left((z+N/z)\eta^{-2}\right),

which is covered by the matrix input sizes up to polylogarithmic factors. Array initialization and all sliding-window updates cost O(Nlog⁡2N)O(N\log^2 N) over the O(log⁡N)O(\log N) repetitions. All intermediate product outputs, exact corrections, scalar factors, and medians require O~(N)\widetilde{O}(N) further work.

Completing the algorithm

The exact bounded-distance handoff

We use the deterministic exact algorithm of [5 Theorem 1]. On the balanced inputs considered here, it returns every distance at most kk exactly and certifies that the others exceed kk, in time

O~(N+kN).(23)\widetilde{O}(N+k\sqrt{N}). \tag*{(23)}

Proof of Theorem 1.1. Set z=⌈N⌉z=\lceil\sqrt{N}\rceil. On the original pattern and text, run (23) with k=zk=z and keep all exact answers. Its cost is O~(N)\widetilde{O}(N) since zN=O(N)z\sqrt{N}=O(N). Run Proposition 4.2 with η=ε/16\eta=\varepsilon/16 on the padded pairs of (16). For each remaining alignment i=s+ui=s+u, return E^u,s−z\widehat{E}_{u,s}-z.

For each remaining alignment, S[i]>zS[i]>z. When the sketch succeeds, Lemma 4.1 yields

∣(E^u,s−z)−S[i]∣≤ηEu,s=η(S[i]+z)<2ηS[i]≤εS[i].\left|(\widehat{E}_{u,s}-z)-S[i]\right|\leq\eta E_{u,s}=\eta(S[i]+z)<2\eta S[i]\leq\varepsilon S[i].

All smaller distances, including zeros, are already exact. The simultaneous success probability is at least 1−N−121-N^{-12}, which suffices.

Proposition 4.2 gives the running time in (2). The exact routine and final output scan cost O~(N)\widetilde{O}(N), absorbed because ω(4a)≥2\omega(4a)\geq2. There is no restriction on the fixed a≥0a\geq0: the exact threshold zz is independent of ε\varepsilon.

Substitution of the rectangular bound

For 0≤a≤1/80\leq a\leq1/8, equation (3) gives ω(4a)=2\omega(4a)=2, so the algorithm takes O~(N)\widetilde{O}(N) time. For a≥1/8a\geq1/8, it gives

12ω(4a)≤12+2a+132a.(24)\frac{1}{2}\omega(4a)\leq\frac{1}{2}+2a+\frac{1}{32a}. \tag*{(24)}

The right-hand side is below the previous exponent 1+2a/31+2a/3 exactly between the roots (3−3)/16(3-\sqrt{3})/16 and (3+3)/16(3+\sqrt{3})/16. Together with the near-linear extension beyond a=1/12a=1/12, this gives the improvement interval (1/12,(3+3)/16)(1/12,(3+\sqrt{3})/16) stated in the introduction.

The running time in Theorem 1.1 improves with stronger matrix multiplication bounds. For example, ω(1)=2\omega(1)=2 would give O~(N)\widetilde{O}(N) time for every a≤1/4a\leq1/4.

AI disclosure

The results of this paper were obtained in cooperation with GPT 6.1. Model assisted in preparing this write-up. I take full responsibility for the contents of this paper.

References

  1. [1]Karl R. Abrahamson. Generalized string matching. SIAM Journal on Computing, 16(6):1039–1051, 1987. https://epubs.siam.org/doi/10.1137/0216067.DOI
  2. [2]Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. Approximating text-to-pattern Hamming distances, 2020. https://arxiv.org/html/2001.00211.
  3. [4]Nick Fischer, Yael Kirkpatrick, and Vasileios Nakos. Faster approximate text-to-pattern Hamming distances via near-optimal sumset estimation. arXiv preprint arXiv:2611.05725, 2026. https://arxiv.org/abs/2611.05725.
  4. [5]Pawel Gawrychowski and Przemysław Uznański. Towards unified approximate pattern matching for Hamming and L₁ distance. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics, pages 62:1–62:13, 2018. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.62.DOI
  5. [6]Mikkel Thorup. High speed hashing for integers and strings, 2015. https://arxiv.org/pdf/1504.06804v9.
  6. [7]Przemysław Uznański. Rectangular matrix multiplication from polynomial products, 2026. https://arxiv.org/abs/2610.10494v2.

Paper details

vlnc:W_evj4dj4s
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT 6.1

View statement
Looking for related papers…
Contents