Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication.

DOI10.4230/LIPIcs.ICALP.2018.109zbMath1499.68145OpenAlexW2887037685MaRDI QIDQ5002794

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

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9113/pdf/LIPIcs-ICALP-2018-109.pdf/

zbMATH Keywords

pattern matchinghigh-dimensional geometrymatrix multiplicationfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (1)

Approximating Approximate Pattern Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximate pattern matching with thresholds
• Pattern matching in the Hamming distance with thresholds
• \(L_{1}\) pattern matching lower bound
• Fast sparse matrix multiplication
• Dominance Product and High-Dimensional Closest Pair under L_infty
• The Closest Pair Problem under the Hamming Metric
• Automata, Languages and Programming

This page was built for publication: Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication.