Metraipolis › archive › dc_4e5aed4a73ea

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation — arXiv:2611.05725

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05725
License (as archived): CC0-1.0
Archived: 2026-11-05T18:31:32.213Z
SHA-256 of the archived text: 8b67d345b766589c9016c9d6eec61ca4a3a4129ad914e561d6abbdd0c36d9de1
Stable URL of this page: https://metraipolis.com/documento/dc_4e5aed4a73ea

How to cite

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation — arXiv:2611.05725 — arXiv (en), https://arxiv.org/abs/2611.05725 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e5aed4a73ea (Metraipolis archive dc_4e5aed4a73ea, sha256 8b67d345b766589c9016c9d6eec61ca4a3a4129ad914e561d6abbdd0c36d9de1)

BibTeX

@misc{dc4e5aed4a73ea,
  title = {Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation — arXiv:2611.05725},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05725},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e5aed4a73ea; sha256 8b67d345b766589c9016c9d6eec61ca4a3a4129ad914e561d6abbdd0c36d9de1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05725. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance between~$P$ and every length-$|P|$ substring of~$T$. As exact algorithms have been stuck at time~$\tilde O(n^{3/2})$ for decades, a long line of work has turned to the $(1+\epsilon)$-approximate version of the problem. Milestones include Karloff's $\tilde O(\epsilon^{-2} n)$-time algorithm [IPL '93], followed by randomized improvements to $\tilde O(\epsilon^{-1} n)$ by Kopelowitz and Porat [FOCS '15] and recently to $\tilde O(\epsilon^{-0.915} n)$ by Chan, Jin, Vassilevska W., and Xu [FOCS '23]. In this work, we significantly improve this bound to $\tilde O(\epsilon^{-2/3} n)$, using a considerably simpler algorithm. Our algorithm follows the framework of Chan, Jin, Vassilevska W., and Xu, which reduces the problem to a variant of 3SUM that we call \emph{Sumset Estimation}. We solve Sumset Estimation optimally (up to logarithmic factors) by replacing their matrix multiplication techniques with ideas from sparse recovery. Specifically, we adapt the classic Count Sketch by replacing its random signs with random complex roots of unity---a simple idea that may find further applications for other additive problems. Finally, we give evidence that our running time might in fact be optimal: we show that the $\epsilon^{-2/3}$ dependence is \emph{best possible} for a certain natural class of algorithms, including ours and all previous algorithms.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05725 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.022Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).