WorksComputer Science
Approximate Hamming Convolution via Rectangular Matrix Multiplication
Abstract
We study -approximate text-to-pattern Hamming distance: given a length- pattern and a length- text, compute the Hamming distance at every alignment to relative error . For every fixed and , we give a randomized algorithm with simultaneous high-probability correctness on a logarithmic-word RAM and expected running time , where suppresses subpolynomial factors and is the exponent for multiplying an matrix by an matrix. With a recent rectangular bound, this improves the published bounds [CGK+20, FKN26] for . In particular, the algorithm runs in expected time for , extending the previous near-linear guarantee through .
Introduction and results
For equal-length strings over an integer alphabet , their Hamming distance is
Given a text and a pattern , where , their text-to-pattern Hamming distance is the array
We use zero-based indices and half-open substrings. For , a -approximation is an array with for every .
By the standard blocking reduction, we may assume and . We require simultaneous correctness at all alignments with high probability. The alphabet has size , and symbols occupy bits. Reversing the pattern expresses the equality counts as convolution coefficients; this accounts for the term Hamming convolution.
We use a word RAM with -bit words and include all preprocessing and output costs. Throughout, suppresses subpolynomial factors in the input length, including polylogarithmic factors. We write for fixed when stating our running-time bounds. Our algorithm improves the published running-time bounds for .
Main result
Let denote the arithmetic exponent for multiplying an matrix by a matrix over the rationals. The shape parameter is fixed, and every fixed positive exponent slack is permitted. We use the same for word-RAM multiplication of polynomially bounded integer matrices. Reading the matrices and writing their product are included; the size bound covers these costs.
Theorem 1.1. Fix and set . For all sufficiently large , all distances in (1) admit simultaneous relative- estimates with probability at least in expected time
The sketch overhead is polylogarithmic independently of ; constants may depend on 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 .
Improvement range
For the numerical consequence, we use rectangular bound [7 Corollary 1.2]:
These arithmetic bounds hold over fields of characteristic zero, including the rationals. Substituting (3) into Theorem 1.1 gives, for , running time
For , the same theorem gives running time . The stated Corollary 9.2 of [2], with matrix dual exponent , guarantees near-linear time through . The new algorithm improves the cited published bounds throughout . 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 . With the matrix dual-exponent bound , this guarantees time through . Our algorithm extends the guarantee to . 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 .
Abrahamson [1] gives the classical exact algorithm. Chan, Jin, Vasilevska Williams, and Xu [CJWWX23] remove logarithmic factors, obtaining an Las Vegas algorithm, and give a uniform approximation bound with inverse-accuracy exponent . Fischer, Kirkpatrick, and Nakos [4] give the stronger uniform bound . We use their approximation bound as a comparison benchmark.
To compare the approximation exponent with matrix multiplication, let be the infimum achievable running-time exponent for relative error , with the computational model and simultaneous success guarantee of Theorem 1.1. Our result implies
The reduction in [5 Section 4, Corollary 13] further implies
Binary partitions of randomly permuted positions
Write . For set
Choose a uniformly random odd and let . Since is odd, permutes . For every power of two , partition the permuted positions into consecutive intervals:
Bucket at level has children and at level . At the final level , 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 and every power of two ,
Proof. The case is immediate. Write , where is a power of two and is odd. As varies, the cyclic difference is uniform over the odd multiples of . Put . A collision requires this difference to lie in or . If , neither event is possible. Otherwise is an even integer, and each end interval contains eligible values. Their total probability is at most .
A sketch from binary addition
Fix strings . Encode symbols injectively as vectors in , where , and put . Exactly of these vectors are nonzero. Extend the sequence by zeros to length , and arrange it at the leaves of the binary interval tree in permuted order. For a zero-padded string , write for the XOR of its codes at positions with .
For bits at the leaves of any full binary tree, let be the XOR of the bits below node . At each internal node, , so the identity gives
Summing over internal nodes gives
Write for the total XOR of a string and set
where is a uniform linear functional. We compute this root contribution exactly.
Complementary labels and the estimator
For , take
At each internal depth , draw samples. Each sample sets , chooses a uniform parent and a fresh uniform linear functional , and assigns each string the label
The multiplier is shared; all masks and sampled parents are independent conditional on .
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 , and encode the bitwise complement of a column label by a Boolean one-hot vector. Concatenate the encodings into matrices of inner dimension . Define each estimate directly by
Row entries are at most , column entries are Boolean, and product entries are at most .
Lemma 3.1 (Unbiasedness and accuracy). Fix a pair and write and . For every fixed multiplier , . For ,
and . If , then always.
Proof. For one sample at depth , put
The row and column labels are complements exactly when . Its contribution to the product entry is therefore
For a fixed mask , let be the parity of the bits below node . By (10) and the tree identity,
Here every fixed nonzero word has -value one with probability .
A nonzero internal-node sample requires at least two mismatches in its sampled parent. A fixed pair shares a parent with probability at most by Lemma 2.1, and that parent is sampled with probability . A union bound gives
These expectations include , the parent, and . Conditional independence and the conditional mean therefore give
Chebyshev and (11) give the stated failure probability. For , every two-child product is zero and .
Repeat the entire construction, including the multiplier, times independently and take a median for each pair. For any fixed pairs with , amplification and a union bound give simultaneous relative- accuracy with failure at most . Pairs may share all the randomness. Counting both children, the total number of bit coordinates on either side is
Batching shifted strings by matrix multiplication
An exact padding offset
Fix an integer and a new symbol . Append copies of a genuine symbol, for example , to , obtaining . Define length- strings
These strings are implicit. Each requested shift is uniquely with . Only pairs with are used.
Lemma 4.1 (Exact padding offset). Writing , every used pair satisfies
Proof. At positions , the comparisons are exactly those of alignment . They lie in the original text because . At the other positions, contains and 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 as zero and genuine symbols as distinct nonzero binary vectors. Fix a repetition’s multiplier and . Form the length- pattern array and maintain the moving text array
For a circular interval in , write and for the XORs of the array entries it contains. Prefix XORs of answer each such query in constant time, splitting a wrapping interval into at most two intervals. Constructing and its prefixes costs . Maintain in a binary tree storing the XOR of each dyadic interval. A point update changes one node per level, and a range query uses such intervals, so each operation takes time. Sweep increasing block starts , removing text positions that leave and inserting those that enter. There are updates over the entire sweep, costing including initialization. One tree serves every partition level.
The bucket XORs of the padded strings satisfy
Here interval translations are modulo . Indeed, the pattern symbol at position is mapped to , and the text symbol at relative position is mapped to . Translated intervals retain their length, although their endpoints need not be aligned with the partition. The text array uses absolute text positions, reduced modulo . 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 is encoded as zero, for every row. The exact root correction is therefore
independent of . Compute all from the total XOR of and prefix XORs of in time. For each repetition, form and evaluate
Then take medians across repetitions.
Proposition 4.2 (Cost of the batched sketches). Fix and let . For , all padded distances in (16) can be estimated to relative error , simultaneously with failure probability at most , in time
Proof. There are rows and columns, hence 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 . Process repetitions separately. Partition each product’s inner dimension into blocks of length and pad the final block. The total number of resulting matrix products is polylogarithmic. Each product has dimensions . Taking , this costs 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 time. By (15), the total feature construction cost, apart from preprocessing, is
which is covered by the matrix input sizes up to polylogarithmic factors. Array initialization and all sliding-window updates cost over the repetitions. All intermediate product outputs, exact corrections, scalar factors, and medians require 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 exactly and certifies that the others exceed , in time
Proof of Theorem 1.1. Set . On the original pattern and text, run (23) with and keep all exact answers. Its cost is since . Run Proposition 4.2 with on the padded pairs of (16). For each remaining alignment , return .
For each remaining alignment, . When the sketch succeeds, Lemma 4.1 yields
All smaller distances, including zeros, are already exact. The simultaneous success probability is at least , which suffices.
Proposition 4.2 gives the running time in (2). The exact routine and final output scan cost , absorbed because . There is no restriction on the fixed : the exact threshold is independent of .
Substitution of the rectangular bound
For , equation (3) gives , so the algorithm takes time. For , it gives
The right-hand side is below the previous exponent exactly between the roots and . Together with the near-linear extension beyond , this gives the improvement interval stated in the introduction.
The running time in Theorem 1.1 improves with stronger matrix multiplication bounds. For example, would give time for every .
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]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]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.
- [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.
- [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
- [6]Mikkel Thorup. High speed hashing for integers and strings, 2015. https://arxiv.org/pdf/1504.06804v9.
- [7]Przemysław Uznański. Rectangular matrix multiplication from polynomial products, 2026. https://arxiv.org/abs/2610.10494v2.