Imagen de Portada

Almost Linear Size Edit Distance Sketch

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Koucký, Michal, Saks, Michael
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Many Flavors of Edit Distance
por: Bhattacharya, Sudatta, et al.
Publicado: (2024)

SquareSort: a cache-oblivious sorting algorithm
por: Koucký, Michal, et al.
Publicado: (2024)

Nearly Optimal List Labeling
por: Bender, Michael A., et al.
Publicado: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
por: Khanna, Sanjeev, et al.
Publicado: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
por: Das, Debarati, et al.
Publicado: (2025)

Path-Reporting Distance Oracles with Linear Size
por: Neiman, Ofer, et al.
Publicado: (2024)

Distances in Planar Graphs are Almost for Free!
por: Mozes, Shay, et al.
Publicado: (2026)

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

Pattern Matching under Weighted Edit Distance
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2025)

Hardness of Dynamic Tree Edit Distance and Friends
por: Hu, Bingbing, et al.
Publicado: (2025)

Approximate Circular Pattern Matching under Edit Distance
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2024)

String Sanitization Under Edit Distance: Improved and Generalized
por: Mieno, Takuya, et al.
Publicado: (2020)

Deterministic Mincut in Almost-Linear Time
por: Li, Jason
Publicado: (2021)

Network Unreliability in Almost-Linear Time
por: Cen, Ruoxu, et al.
Publicado: (2025)

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

Approximating Directed Connectivity in Almost-Linear Time
por: Quanrud, Kent
Publicado: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
por: Assadi, Sepehr, et al.
Publicado: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
por: Chmel, Petr, et al.
Publicado: (2026)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
por: Mao, Xiao, et al.
Publicado: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
por: Boneh, Itai, et al.
Publicado: (2025)

Multipass Linear Sketches for Geometric LP-Type Problems
por: Çekirge, N. Efe, et al.
Publicado: (2025)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
por: Gribelyuk, Elena, et al.
Publicado: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
por: Abboud, Amir, et al.
Publicado: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
por: Li, George Z., et al.
Publicado: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
por: Yoshida, Yuichi
Publicado: (2026)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
por: Gorbachev, Egor, et al.
Publicado: (2024)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
por: Bhattacharya, Sudatta, et al.
Publicado: (2025)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
por: Elkin, Michael, et al.
Publicado: (2023)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
por: Gribelyuk, Elena, et al.
Publicado: (2024)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2025)

The Case for External Graph Sketching
por: Bender, Michael A., et al.
Publicado: (2025)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
por: Bucić, Matija, et al.
Publicado: (2025)

Simple Linear-Size Additive Emulators
por: Hoppenworth, Gary
Publicado: (2023)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
por: Dudeja, Aditi, et al.
Publicado: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
por: Brand, Jan van den, et al.
Publicado: (2024)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
por: Liu, Yang P.
Publicado: (2025)

Local Enumeration: The Not-All-Equal Case
por: Gurumukhani, Mohit, et al.
Publicado: (2025)

Faster Linear-Size And-Or Path and Adder Circuits
por: Brenner, Ulrich, et al.
Publicado: (2024)

Average-Distortion Sketching
por: Bao, Yiqiao, et al.
Publicado: (2024)

On Sketching Trimmed Statistics
por: Lin, Honghao, et al.
Publicado: (2025)