2026-09-27T05:20:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25927 2026-09-23T23:55:59Z ddc:004 open_access

Hamming Distance Oracles Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Porat, Ely Hamming distance Fine-grained complexity Data structure Oracle In this paper, we present and study the Hamming distance oracle problem. In this problem, the task is to preprocess two strings S and T of lengths n and m, respectively, to obtain a data structure that is able to return the Hamming distance between a substring of S and a substring of T. For strings over a constant-size alphabet, we show that for every x ≤ min{n,m} there is a data structure with Õ(nm/x) preprocessing time and O(x) query time. We also provide a conditional lower bound, showing that for every ε > 0 there is no combinatorial data structure with query time O(x) and preprocessing time O((nm/x)^{1-ε}) unless combinatorial fast matrix multiplication is possible. For strings over a general alphabet, we present a data structure with Õ(nm/√x) pre-processing time and O(x) query time for every x ≤ min {n,m}. Moreover, for every ε > 0 we provide a data structure with a preprocessing time of Õ((n+m)/ε³) that returns with high probability a (1±ε) approximation of the Hamming distance of two input substrings. The query time of the approximation data structure is Õ(1/ε²). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Boneh and Dvir Fried and Shay Golan and Matan Kraus and Ely Porat 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.1 urn:nbn:de:0030-drops-259278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode