Cover Image

Low Sensitivity Hopsets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ashvinkumar, Vikrant, Bernstein, Aaron, Deng, Chengyuan, Gao, Jie, Wein, Nicole
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

A Unified Framework for Hopsets and Spanners
by: Neiman, Ofer, et al.
Published: (2021)

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

Reducing Shortcut and Hopset Constructions to Shallow Graphs
by: Haeupler, Bernhard, et al.
Published: (2025)

Improved Online Sorting
by: Nirjhor, Jubayer, et al.
Published: (2025)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
by: Bernstein, Aaron, et al.
Published: (2025)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
by: Ashvinkumar, Vikrant, et al.
Published: (2023)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
by: Deng, Chengyuan, et al.
Published: (2025)

Bounding the Fragmentation of B-Trees Subject to Batched Insertions
by: Bender, Michael A., et al.
Published: (2026)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

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

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

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

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

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Improving the Threshold for Finding Rank-1 Matrices in a Subspace
by: Dastidar, Jeshu, et al.
Published: (2025)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Matching Composition and Efficient Weight Reduction in Dynamic Matching
by: Bernstein, Aaron, et al.
Published: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

DAG Covers: The Steiner Point Effect
by: Bhore, Sujoy, et al.
Published: (2026)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2025)

On the Price of Differential Privacy for Hierarchical Clustering
by: Deng, Chengyuan, et al.
Published: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)

A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
by: Singhal, Vikrant
Published: (2023)