Approximate Hamming Convolution via Rectangular Matrix Multiplication

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