betaFeedback

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.

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

where O~\widetilde{O} suppresses subpolynomial factors and ω(k)\omega(k) is the exponent for multiplying an n×nkn \times n^k matrix by an nk×nn^k \times n matrix. With rectangular bound [10], this improves the published bounds [2, 5] 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 \le1/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.

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]:

ω(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.

Corollary 1.2. For 0≤a≤1/80 \le a \le1/8, all alignments can be approximated in expected time O~(N)\widetilde{O}(N). For a≥1/8a \ge1/8, the running time is O~(N1/2+2a+1/(32a))\widetilde{O}(N^{1/2+2a+1/(32a)}).

Proof. Substitute k=4ak=4a in (3) and halve the exponent as in Theorem 1.1. □

For a≥1/8a \ge1/8, the exponent in the corollary is below the 1+2a/31+2a/3 bound of [5] up to their intersection at (3+3)/16(3+\sqrt{3})/16. If ω(1)=2\omega(1)=2, Theorem 1.1 gives near-linear time through a=1/4a=1/4.

Previous work and the scope of the comparison

Kopelowitz and Porat approximated all text-to-pattern Hamming distances to relative error ε\varepsilon with high probability in O~(n/ε)\widetilde{O}(n/\varepsilon) time [7 Theorem 1]. Their simpler algorithm hashes the alphabet to O(1/ε)O(1/\varepsilon) symbols and computes the projected distances by convolution, giving the same guarantee in O((n/ε)log⁡nlog⁡m)O((n/\varepsilon)\log n\log m) 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 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 also groups shifts into rows and columns. Each sketch coordinate records the parities of two interval counts. For small distances we use the deterministic kk-mismatch algorithm of Clifford, Fontaine, Porat, Sach, and Starikovskaya, which already runs in near-linear time for k=Nk=\sqrt{N} [4 Theorem 1]. Gawrychowski and Uznański later improved the bound for larger kk to O~(N+kN)\widetilde{O}(N+k\sqrt{N}) on balanced inputs [6 Theorem 1].

Abrahamson [Abr87] gives the classical exact O~(N3/2)\widetilde{O}(N^{3/2}) algorithm. Chan, Jin, Vassilevska Williams, and Xu [3] 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 [5] 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 [6 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)}

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 N\sqrt{N} is an even integer.1 Write [m]={0,…,m−1}[m]=\{0,\ldots,m-1\}. Each shift is uniquely i=s+ui=s+u, where ss is the block start, a multiple of N\sqrt{N}, and u∈[N]u\in[\sqrt{N}] is the offset. All offsets in a block use the same text window of length M=N+NM=N+\sqrt{N} starting at ss. Append N\sqrt{N} copies of P[0]P[0] to TT, forming T′T', so that the last window is defined as well.

Sort the σ≤3N\sigma\le3N distinct symbols of PP and TT and relabel them 0,…,σ−10,\ldots,\sigma-1 in that order. Encode symbol cc at position jj by the key κ(j,c)=j+4Nc\kappa(j,c)=j+4Nc. All positions used below lie in [4N][4N], so a key determines both its position and its symbol. Using positions relative to the window, define the pattern set at offset uu and the text set at block start ss by

Au={κ(j+u,P[j]):j∈[N]},A_u=\{\kappa(j+u,P[j]):j\in[N]\},
Bs={κ(t−s,T′[t]):s≤t<s+M},s=0,N,2N,…, s≤N.B_s=\{\kappa(t-s,T'[t]):s\le t<s+M\},\qquad s=0,\sqrt{N},2\sqrt{N},\ldots,\ s\le N.

At a valid shift i=s+u≤Ni=s+u\le N, pattern position jj meets text position t=i+jt=i+j. Both keys use the position j+u=t−sj+u=t-s. A match therefore cancels from Au△BsA_u\triangle B_s, while a mismatch contributes two keys. The N\sqrt{N} window positions outside the aligned pattern each contribute one text key. Thus the symmetric difference has even size and

∣Au△Bs∣2=S[s+u]+N2.(6)\frac{\lvert A_u\triangle B_s\rvert}{2}=S[s+u]+\frac{\sqrt{N}}{2}. \tag*{(6)}

Now take the indicator vectors of the AuA_u as rows and those of the BsB_s as columns, with one coordinate for each of the 4Nσ4N\sigma possible keys. At a valid shift, the ordinary dot product counts the N−S[s+u]N-S[s+u] matches. Summing the coordinatewise XORs gives the row–column Hamming distance ∣Au△Bs∣\lvert A_u\triangle B_s\rvert. Equation (6) therefore reduces all alignments to this generalized matrix product. The N\sqrt{N} rows and N+1\sqrt{N}+1 columns contain Θ(N3/2)\Theta(N^{3/2}) ones in total. Sections 3 and 4 sketch the sets directly from P,TP,T and estimate these distances using one ordinary integer matrix product per repetition.

Estimating the size of a set

Choose U=2dU = 2^d to be the smallest power of two at least 4N(σ+1)4N(\sigma+ 1). All keys lie in [U][U], and d=O(log⁡N)d = O(\log N). We use the binary interval tree on [U][U], whose 2j2^j nodes at depth jj are intervals of equal size.

For a uniform odd μ∈[U]\mu\in[U], put π(x)=μx mod U\pi(x) = \mu x \bmod U. At a depth with p=2jp = 2^j nodes, two distinct keys x,yx,y land in the same interval with probability at most 2/p2/p by multiply-shift hashing [9 Section 2.3]. Indeed, if gg is the largest power of two dividing x−yx-y, then μ(x−y) mod U\mu(x-y) \bmod U is uniform over the U/(2g)U/(2g) odd multiples of gg in [U][U]. A collision requires a cyclic distance less than W=U/pW = U/p. For p≥2p \ge2 this is impossible if W≤gW \le g, and otherwise at most W/gW/g of the possible differences qualify. The case p=1p = 1 is immediate.

Lemma 3.1 (Set cardinality). Let C⊆[U]C \subseteq[U], where U=2dU = 2^d and d≥1d \ge1, and put H=∣C∣H = |C|. Fix η>0\eta> 0. Choose a uniform odd μ∈[U]\mu\in[U] and mark the leaves π(C)\pi(C), where π(x)=μx mod U\pi(x) = \mu x \bmod U. Make L=⌈12d2/η2⌉L = \left\lceil12d^2/\eta^2 \right\rceil independent draws using this multiplier. Draw ℓ\ell chooses a uniform depth jℓ∈{0,…,d−1}j_\ell\in\{0,\ldots,d-1\} and then a uniform node at that depth.

Let λℓ(C)\lambda_\ell(C) be the two parity bits for the numbers of marked leaves in the left and right children of that node, respectively. The sketch is sk⁡(C)=(b(C),λ1(C),…,λL(C))\operatorname{sk}(C) = (b(C), \lambda_1(C), \ldots, \lambda_L(C)), where b(C)=∣C∣ mod 2b(C) = |C| \bmod2. Define the cardinality estimate by

ξ(C)=b(C)+2L∑ℓ=1Ld2jℓ1{λℓ(C)=(1,1)}.(7)\xi(C) = b(C) + \frac{2}{L}\sum_{\ell=1}^{L} d2^{j_\ell}\mathbf{1}_{\{\lambda_\ell(C)=(1,1)\}}. \tag*{(7)}

Then E[ξ(C)∣μ]=H\mathbb{E}[\xi(C)\mid\mu] = H for every μ\mu, and with probability at least 2/32/3 over the multiplier and the draws, ∣ξ(C)−H∣≤ηH|\xi(C)-H| \le\eta H.

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 b(C)b(C) unpaired leaves, so (H−b(C))/2(H-b(C))/2 nodes form a pair. Conditional on μ\mu, a node at depth jj is drawn with probability 1/(d2j)1/(d2^j). Its weight d2jd2^j cancels this probability. Thus the expected weighted indicator in each draw is (H−b(C))/2(H-b(C))/2, proving the mean identity.

Let ZZ be the weighted indicator for one draw. Fix its depth jj and put p=2jp = 2^j. A nonzero contribution requires two marked keys in the sampled interval. A fixed pair of keys shares an interval with probability at most 2/p2/p over μ\mu, and that interval is selected with probability 1/p1/p. Hence

E[Z2∣j]≤(dp)22(H2)p2≤d2H2.\mathbb{E}[Z^2\mid j] \le(dp)^2\frac{2\binom{H}{2}}{p^2} \le d^2H^2.

The draws are independent conditional on μ\mu, and their conditional mean is the same for every μ\mu. It follows that Var⁡ξ(C)=4Eμ[Var⁡(Z∣μ)]/L≤4d2H2/L\operatorname{Var}\xi(C) = 4\mathbb{E}_{\mu}[\operatorname{Var}(Z\mid\mu)]/L \le4d^2H^2/L. For H>0H > 0, Chebyshev bounds the failure probability by 4d2/(Lη2)≤1/34d^2/(L\eta^2) \le1/3. For H=0H = 0 the estimate is zero. □\square

Sketching a symmetric difference. Use the same multiplier and sampled nodes for AA and BB. 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

sk⁡(A△B)=sk⁡(A)⊕sk⁡(B).\operatorname{sk}(A\mathbin{\triangle}B)=\operatorname{sk}(A)\oplus\operatorname{sk}(B).

For the application in § 2, H=∣A△B∣H = |A\mathbin{\triangle}B| is even, so b(A△B)=0b(A\mathbin{\triangle}B)=0. The XOR of two labels equals (1,1)(1,1) exactly when they are bitwise complements. Thus (7) gives

ξ(A△B)2=1L∑ℓ=1Ld2jℓ1{λℓ(A)=λℓ(B)‾},(8)\frac{\xi(A\mathbin{\triangle}B)}{2} = \frac{1}{L}\sum_{\ell=1}^{L}d2^{j_\ell}\mathbf{1}_{\{\lambda_\ell(A)=\overline{\lambda_\ell(B)}\}}, \tag*{(8)}

where the bar flips both bits.

Batching all alignments

Range counts for the shifted sets. Fix the multiplier μ\mu. Each bit of a label λℓ(C)\lambda_\ell(C) is the parity of ∣π(C)∩I∣|\pi(C) \cap I| for one of the two child intervals II. The whole-set parities are known from ∣Au∣=N|A_u| = N and ∣Bs∣=N+N|B_s| = N + \sqrt{N}. To answer the interval queries for every shift, put pj=π(κ(j,P[j]))p_j = \pi(\kappa(j, P[j])) and qt=π(κ(t,T′[t]))q_t = \pi(\kappa(t, T'[t])). Shifting a position by hh adds μh\mu h to its permuted key modulo UU. Thus, with interval translations taken modulo UU,

∣π(Au)∩I∣=∣{j∈[N]:pj∈I−μu}∣,∣π(Bs)∩I∣=∣{t∈[s,s+M):qt∈I+μs}∣.(9)\begin{aligned} |\pi(A_u) \cap I| &= |\{j \in[N] : p_j \in I - \mu u\}|,\\ |\pi(B_s) \cap I| &= |\{t \in[s, s + M) : q_t \in I + \mu s\}|. \tag*{(9)} \end{aligned}

The pattern uses positions j+uj + u, while the text window uses positions t−st - s, which gives the two signs.

For the first count, sort the pjp_j and find the interval endpoints by binary search in O(log⁡N)O(\log N) time. The second count is a rectangle query on the points (t,qt)(t, q_t). Build a balanced binary tree on tt and store at each node the sorted qtq_t values in its subtree. The window [s,s+M)[s, s + M) decomposes into O(log⁡N)O(\log N) nodes, so binary searches in their lists take O(log⁡2N)O(\log^2 N) time. In either query, a translated interval that wraps around UU splits into two ordinary intervals. Building both structures takes O(Nlog⁡N)O(N \log N) 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 L≥1L \ge1 sampled nodes, one can generate in O~(N+NL)\widetilde{O}(N+\sqrt{N}L) total time a N×4L\sqrt{N} \times4L integer matrix VV from the row sets AuA_u and a 4L×(N+1)4L \times(\sqrt{N}+1) integer matrix WW from the column sets BsB_s. Their product satisfies (VW)u,s/L=ξ(Au△Bs)/2(VW)_{u,s}/L = \xi(A_u \triangle B_s)/2 for every u,su,s.

Proof. Process one sampled node at a time, generating four columns of VV and four rows of WW. By (9), two range counts give each two-bit label. There are 2N+12\sqrt{N}+1 labels per node, so the preprocessing and label construction take O~(N+NL)\widetilde{O}(N+\sqrt{N}L) time.

Index the four coordinates of block ℓ\ell by the two-bit labels. In row uu put weight d 2jℓd\,2^{j\ell} at λℓ(Au)\lambda_\ell(A_u), and in column ss put weight 11 at λℓ(Bs)\lambda_\ell(B_s). Set the other coordinates in each block to zero. Summing the block dot products gives L ξ(Au△Bs)/2L\,\xi(A_u \triangle B_s)/2 by (8). The integer weights are at most dUdU, and every product entry is at most LdULdU.

Proof of Theorem 1.1. Take η=ε/2\eta= \varepsilon/2, so Lemma 3.1 uses L=⌈48d2N2a⌉L = \lceil48d^2N^{2a}\rceil samples. Repeat the construction of Proposition 4.1 independently O(log⁡N)O(\log N) times, drawing a new multiplier each time. Lemma 3.1, medians and a union bound over the N+1N+1 valid shifts give simultaneous relative-η\eta estimates of ∣Au△Bs∣/2|A_u \triangle B_s|/2 with failure probability at most N−10N^{-10}.

On our length-NN pattern and length-2N2N text, the kk-mismatch algorithm of Clifford et al. [4 Theorem 1.1] takes O~(N+k2)\widetilde{O}(N+k^2) time. With k=Nk = \sqrt{N}, it returns all distances S[i]≤NS[i] \le\sqrt{N} exactly and identifies them in O~(N)\widetilde{O}(N) time. Keep its exact answers. For S[i]>NS[i] > \sqrt{N}, subtract N/2\sqrt{N}/2 from the median for i=s+ui = s + u. By (6), the absolute error is at most η(S[i]+N/2)<3εS[i]/4\eta(S[i] + \sqrt{N}/2) < 3\varepsilon S[i]/4 on the simultaneous success event.

Both outer matrix dimensions are O(N)O(\sqrt{N}). The inner dimension is O(N2alog⁡2N)O(N^{2a}\log^2 N), so splitting it into blocks of length ⌈N2a⌉\lceil N^{2a}\rceil takes only polylogarithmically many products. For fixed aa, the matrix indices and the product entries (bounded by LdULdU) have O(log⁡N)O(\log N) bits, so the word-RAM convention of § 1 applies. The products take O~(Nω(4a)/2)\widetilde{O}(N^{\omega(4a)/2}) time. The input and output size bound ω(4a)≥max⁡{2,1+4a}\omega(4a) \ge\max\{2,1+4a\} 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

  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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
  6. [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
  7. [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.
  8. [9]Mikkel Thorup. High speed hashing for integers and strings, 2015. https://arxiv.org/pdf/1504.06804v9.
  9. [10]Przemysław Uznański. Rectangular matrix multiplication from polynomial products, 2026. https://arxiv.org/abs/2610.10494v2.

Paper details

vlnc:W_evj4dj4s
Version
v2 · latest
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