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 .
where suppresses subpolynomial factors and is the exponent for multiplying an matrix by an matrix. With rectangular bound [10], this improves the published bounds [2, 5] 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.
We reduce all alignments to a matrix product whose entries are Hamming distances between binary rows and columns. Their supports are sets of position–symbol pairs. Each mismatch contributes two keys to the symmetric difference, and padding contributes a known even number. Pair the surviving keys from the leaves of a binary tree upwards. A node forms a pair exactly when both children have odd counts. Sampling these nodes estimates all entries with one ordinary integer matrix product per repetition.
Improvement range
For the numerical consequence, we use rectangular bound [10 Corollary 1.2]:
These arithmetic bounds hold over fields of characteristic zero, including the rationals.
Corollary 1.2. For , all alignments can be approximated in expected time . For , the running time is .
Proof. Substitute in (3) and halve the exponent as in Theorem 1.1. □
For , the exponent in the corollary is below the bound of [5] up to their intersection at . If , Theorem 1.1 gives near-linear time through .
Previous work and the scope of the comparison
Kopelowitz and Porat approximated all text-to-pattern Hamming distances to relative error with high probability in time [7 Theorem 1]. Their simpler algorithm hashes the alphabet to symbols and computes the projected distances by convolution, giving the same guarantee in time [8 Theorem 2].
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 also groups shifts into rows and columns. Each sketch coordinate records the parities of two interval counts. For small distances we use the deterministic -mismatch algorithm of Clifford, Fontaine, Porat, Sach, and Starikovskaya, which already runs in near-linear time for [4 Theorem 1]. Gawrychowski and Uznański later improved the bound for larger to on balanced inputs [6 Theorem 1].
Abrahamson [Abr87] gives the classical exact algorithm. Chan, Jin, Vassilevska Williams, and Xu [3] remove logarithmic factors, obtaining an Las Vegas algorithm, and give a uniform approximation bound with inverse-accuracy exponent . Fischer, Kirkpatrick, and Nakos [5] 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 [6 Section 4, Corollary 13] further implies
Alignments as even sets
At a given alignment, we want a pattern set and a text set with one common key per match. We group shifts into blocks so that each pattern set serves a row of alignments and each text set serves a column. Without loss of generality, assume that is an even integer.1 Write . Each shift is uniquely , where is the block start, a multiple of , and is the offset. All offsets in a block use the same text window of length starting at . Append copies of to , forming , so that the last window is defined as well.
Sort the distinct symbols of and and relabel them in that order. Encode symbol at position by the key . All positions used below lie in , so a key determines both its position and its symbol. Using positions relative to the window, define the pattern set at offset and the text set at block start by
At a valid shift , pattern position meets text position . Both keys use the position . A match therefore cancels from , while a mismatch contributes two keys. The window positions outside the aligned pattern each contribute one text key. Thus the symmetric difference has even size and
Now take the indicator vectors of the as rows and those of the as columns, with one coordinate for each of the possible keys. At a valid shift, the ordinary dot product counts the matches. Summing the coordinatewise XORs gives the row–column Hamming distance . Equation (6) therefore reduces all alignments to this generalized matrix product. The rows and columns contain ones in total. Sections 3 and 4 sketch the sets directly from and estimate these distances using one ordinary integer matrix product per repetition.
Estimating the size of a set
Choose to be the smallest power of two at least . All keys lie in , and . We use the binary interval tree on , whose nodes at depth are intervals of equal size.
For a uniform odd , put . At a depth with nodes, two distinct keys land in the same interval with probability at most by multiply-shift hashing [9 Section 2.3]. Indeed, if is the largest power of two dividing , then is uniform over the odd multiples of in . A collision requires a cyclic distance less than . For this is impossible if , and otherwise at most of the possible differences qualify. The case is immediate.
Lemma 3.1 (Set cardinality). Let , where and , and put . Fix . Choose a uniform odd and mark the leaves , where . Make independent draws using this multiplier. Draw chooses a uniform depth and then a uniform node at that depth.
Let be the two parity bits for the numbers of marked leaves in the left and right children of that node, respectively. The sketch is , where . Define the cardinality estimate by
Then for every , and with probability at least over the multiplier and the draws, .
Proof. Pair marked leaves from the bottom up, passing one unpaired leaf to the parent whenever a subtree contains an odd number. A node forms one pair exactly when both children have odd counts. The root has unpaired leaves, so nodes form a pair. Conditional on , a node at depth is drawn with probability . Its weight cancels this probability. Thus the expected weighted indicator in each draw is , proving the mean identity.
Let be the weighted indicator for one draw. Fix its depth and put . A nonzero contribution requires two marked keys in the sampled interval. A fixed pair of keys shares an interval with probability at most over , and that interval is selected with probability . Hence
The draws are independent conditional on , and their conditional mean is the same for every . It follows that . For , Chebyshev bounds the failure probability by . For the estimate is zero.
Sketching a symmetric difference. Use the same multiplier and sampled nodes for and . In every tree interval, keys common to both sets contribute twice to the sum of their counts. Taking parities, in the whole tree and in each sampled child, gives the bitwise identity
For the application in § 2, is even, so . The XOR of two labels equals exactly when they are bitwise complements. Thus (7) gives
where the bar flips both bits.
Batching all alignments
Range counts for the shifted sets. Fix the multiplier . Each bit of a label is the parity of for one of the two child intervals . The whole-set parities are known from and . To answer the interval queries for every shift, put and . Shifting a position by adds to its permuted key modulo . Thus, with interval translations taken modulo ,
The pattern uses positions , while the text window uses positions , which gives the two signs.
For the first count, sort the and find the interval endpoints by binary search in time. The second count is a rectangle query on the points . Build a balanced binary tree on and store at each node the sorted values in its subtree. The window decomposes into nodes, so binary searches in their lists take time. In either query, a translated interval that wraps around splits into two ordinary intervals. Building both structures takes time and space per multiplier by sorting the pattern keys and merging the text lists bottom up.
Proposition 4.1. Given the shared multiplier and sampled nodes, one can generate in total time a integer matrix from the row sets and a integer matrix from the column sets . Their product satisfies for every .
Proof. Process one sampled node at a time, generating four columns of and four rows of . By (9), two range counts give each two-bit label. There are labels per node, so the preprocessing and label construction take time.
Index the four coordinates of block by the two-bit labels. In row put weight at , and in column put weight at . Set the other coordinates in each block to zero. Summing the block dot products gives by (8). The integer weights are at most , and every product entry is at most .
Proof of Theorem 1.1. Take , so Lemma 3.1 uses samples. Repeat the construction of Proposition 4.1 independently times, drawing a new multiplier each time. Lemma 3.1, medians and a union bound over the valid shifts give simultaneous relative- estimates of with failure probability at most .
On our length- pattern and length- text, the -mismatch algorithm of Clifford et al. [4 Theorem 1.1] takes time. With , it returns all distances exactly and identifies them in time. Keep its exact answers. For , subtract from the median for . By (6), the absolute error is at most on the simultaneous success event.
Both outer matrix dimensions are . The inner dimension is , so splitting it into blocks of length takes only polylogarithmically many products. For fixed , the matrix indices and the product entries (bounded by ) have bits, so the word-RAM convention of § 1 applies. The products take time. The input and output size bound also covers feature construction, summing the block products, and taking medians.
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
References
- [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]Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, and Yinzhan Xu. Faster algorithms for text-to-pattern Hamming distances. In 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 2188–2203, 2023. https://arxiv.org/abs/2310.13174.
- [4]Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. The k-mismatch problem revisited. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2039–2052, 2016. https://doi.org/10.1137/1.9781611974331.ch142.
- [5]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.
- [6]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
- [7]Tsvi Kopelowitz and Ely Porat. Breaking the variance: Approximating the Hamming distance in 1/ε time per alignment. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 601–613, 2015. https://ieee-focs.org/FOCS-2015-Papers/8191a601.pdf.DOI
- [8]Tsvi Kopelowitz and Ely Porat. A simple algorithm for approximating the text-to-pattern Hamming distance. In 1st Symposium on Simplicity in Algorithms (SOSA), volume 61 of Open Access Series in Informatics, pages 10:1–10:5, 2018. https://doi.org/10.4230/OASIcs.SOSA.2018.10.
- [9]Mikkel Thorup. High speed hashing for integers and strings, 2015. https://arxiv.org/pdf/1504.06804v9.
- [10]Przemysław Uznański. Rectangular matrix multiplication from polynomial products, 2026. https://arxiv.org/abs/2610.10494v2.