Cover Image

Faster Algorithms for Text-to-Pattern Hamming Distances

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Timothy M., Jin, Ce, Williams, Virginia Vassilevska, Xu, Yinzhan
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

A Refined Laser Method and Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2020)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

Listing 6-Cycles in Sparse Graphs
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Faster Cycle Detection in the Congested Clique
by: Censor-Hillel, Keren, et al.
Published: (2024)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

New Separations and Reductions for Directed Preservers and Hopsets
by: Hoppenworth, Gary, et al.
Published: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
by: Chan, Timothy M.
Published: (2026)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
by: Goldenberg, Elazar, et al.
Published: (2022)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)