Image de couverture de livre

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Khanna, Sanjeev, Konrad, Christian, Putterman, Aaron
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
par: Khanna, Sanjeev, et autres
Publié: (2026)

A Theory of Spectral CSP Sparsification
par: Khanna, Sanjeev, et autres
Publié: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
par: Assadi, Sepehr, et autres
Publié: (2025)

On the Parallel Complexity of Finding a Matroid Basis
par: Khanna, Sanjeev, et autres
Publié: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
par: Khanna, Sanjeev, et autres
Publié: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
par: Khanna, Sanjeev, et autres
Publié: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
par: Khanna, Sanjeev, et autres
Publié: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
par: Khanna, Sanjeev, et autres
Publié: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
par: Khanna, Sanjeev, et autres
Publié: (2025)

Fault-Tolerant Approximate Distance Oracles with a Source Set
par: Dey, Dipan, et autres
Publié: (2025)

Fault-Tolerant ST-Diameter Oracles
par: Bilò, Davide, et autres
Publié: (2023)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
par: Kosinas, Evangelos
Publié: (2025)

Streaming Maximal Matching with Bounded Deletions
par: Khanna, Sanjeev, et autres
Publié: (2025)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
par: Khanna, Sanjeev, et autres
Publié: (2026)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
par: Chuzhoy, Julia, et autres
Publié: (2024)

Hamming Distance Oracle
par: Boneh, Itai, et autres
Publié: (2024)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
par: Elkin, Michael, et autres
Publié: (2023)

Distributed Distance Sensitivity Oracles
par: Manoharan, Vignesh, et autres
Publié: (2024)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
par: Parter, Merav, et autres
Publié: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
par: Haeupler, Bernhard, et autres
Publié: (2024)

Improved Algorithms for Clustering with Noisy Distance Oracles
par: Pradhan, Pinki, et autres
Publié: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2024)

Path-Reporting Distance Oracles with Linear Size
par: Neiman, Ofer, et autres
Publié: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2023)

New Diameter Approximations via Distance Oracle Techniques
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
par: Neiman, Ofer, et autres
Publié: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
par: Chuzhoy, Julia, et autres
Publié: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
par: Khanna, Sanjeev, et autres
Publié: (2025)

Query Complexity of the Metric Steiner Tree Problem
par: Chen, Yu, et autres
Publié: (2022)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
par: Assadi, Sepehr, et autres
Publié: (2024)

Fault-Tolerant Bounded Flow Preservers
par: Bansal, Shivam, et autres
Publié: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
par: Kadria, Avi, et autres
Publié: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
par: Kopelowitz, Tsvi, et autres
Publié: (2023)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
par: Manoharan, Vignesh, et autres
Publié: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
par: He, Jialin, et autres
Publié: (2025)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
par: Horowicz, Noam, et autres
Publié: (2025)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
par: Kuszmaul, William, et autres
Publié: (2024)