Hamming Distance Completeness

DOI10.4230/LIPICS.CPM.2019.14MaRDI QIDQ5088904zbMATH OpenOpenAlexFDO

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

Publication date 18 July 2022

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

zbMATH Keywords

approximate pattern matchingmatrix productsfine grained complexity

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Brief announcement: Hamming distance completeness and sparse matrix multiplication
• The information complexity of Hamming distance
• Algorithms and Computation
• Communication Complexity of Computing the Hamming Distance
• scientific article; zbMATH DE number 2162205

Cites work

• scientific article; zbMATH DE number 5899282 (Why is no real title available?)
• scientific article; zbMATH DE number 5764853 (Why is no real title available?)
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Automata, Languages and Programming
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Computing dominances in \(E^ n\)
• Dominance product and high-dimensional closest pair under \(L_\infty\)
• Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
• Efficient matching of nonrectangular shapes.
• Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
• Faster image template matching in the sum of the absolute value of differences measure
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding, minimizing, and counting weighted subgraphs
• Generalized String Matching
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• On Problems Equivalent to (min,+)-Convolution
• On approximate pattern matching with thresholds
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• Pattern matching in the Hamming distance with thresholds
• Powers of tensors and fast matrix multiplication
• Simple deterministic wildcard matching
• Sparse matrix multiplication and triangle listing in the congested clique model
• The Closest Pair Problem under the Hamming Metric
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• \(L_{1}\) pattern matching lower bound

Cited in

(6)

• Hamming distance between the strings generated by adjacency matrix of a subgraph complementary graph and their sum
• Recent advances in text-to-pattern distance algorithms
• scientific article; zbMATH DE number 2123381 (Why is no real title available?)
• Hamming distance for conjugates
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)

This page was built for publication: Hamming Distance Completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088904)