2026-08-06T13:42:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10485 2024-03-06T10:45:51Z ddc:004 open_access

Hamming Distance Completeness Labib, Karim Uznański, Przemysław Wolleb-Graf, Daniel fine grained complexity approximate pattern matching matrix products We show, given a binary integer function diamond that is piecewise polynomial, that (+,diamond) vector products are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include the dominance and l_{2p+1} distances for constant p. Our results imply equivalence (up to polylog factors) between the complexity of computing All Pairs Hamming Distance, All Pairs l_{2p+1} Distance and Dominance Matrix Product, and equivalence between Hamming Distance Pattern Matching, l_{2p+1} Pattern Matching and Less-Than Pattern Matching. The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are likely to be optimal, given lack of progress in improving upper bounds for Hamming distance in the past 30 years. While reductions between selected pairs of products were presented in the past, our work is the first to generalize them to a general class of functions, showing that a wide class of "intermediate" complexity problems are in fact equivalent. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karim Labib and Przemysław Uznański and Daniel Wolleb-Graf 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.14 urn:nbn:de:0030-drops-104853 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.14 eng https://creativecommons.org/licenses/by/3.0/legalcode