Hamming Distance Completeness

DOI10.4230/LIPICS.CPM.2019.14OpenAlexW2956205473MaRDI QIDQ5088904FDOQ5088904

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

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

zbMATH Keywords

approximate pattern matchingmatrix productsfine grained complexity

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

Cited In (6)

• Recent advances in text-to-pattern distance algorithms
• Title not available (Why is that?)
• Hamming distance for conjugates
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Title not available (Why is that?)
• Hamming distance between the strings generated by adjacency matrix of a subgraph complementary graph and their sum

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)