Hamming Distance Completeness

DOI10.4230/LIPIcs.CPM.2019.14OpenAlexW2956205473MaRDI QIDQ5088904

Daniel Wolleb-Graf, Przemysław Uznański, Karim Labib

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CPM.2019.14

zbMATH Keywords

matrix productsapproximate pattern matchingfine grained complexity

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Unnamed Item, Recent advances in text-to-pattern distance algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximate pattern matching with thresholds
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Simple deterministic wildcard matching
• Computing dominances in \(E^ n\)
• Efficient matching of nonrectangular shapes.
• Pattern matching in the Hamming distance with thresholds
• Sparse matrix multiplication and triangle listing in the congested clique model
• \(L_{1}\) pattern matching lower bound
• Finding, Minimizing, and Counting Weighted Subgraphs
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Powers of tensors and fast matrix multiplication
• Generalized String Matching
• Faster image template matching in the sum of the absolute value of differences measure
• Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
• On Problems Equivalent to (min,+)-Convolution
• Dominance Product and High-Dimensional Closest Pair under L_infty
• The Closest Pair Problem under the Hamming Metric
• Automata, Languages and Programming
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching