research
∙
09/13/2023
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
We study a new and stronger notion of fault-tolerant graph structures wh...
share
research
∙
07/25/2023
Fully Dynamic Consistent k-Center Clustering
We study the consistent k-center clustering problem. In this problem, th...
research
∙
04/18/2023
Parallel Greedy Spanners
A t-spanner of a graph is a subgraph that t-approximates pairwise distan...
research
∙
03/01/2023
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights
This paper presents parallel and distributed algorithms for single-sourc...
research
∙
01/17/2023
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
The packet routing problem asks to select routing paths that minimize th...
research
∙
11/21/2022
A Cut-Matching Game for Constant-Hop Expanders
This paper provides a cut-strategy that produces constant-hop expanders ...
research
∙
10/28/2022
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
We introduce stronger notions for approximate single-source shortest-pat...
research
∙
10/21/2022
A Simple Deterministic Distributed Low-Diameter Clustering
We give a simple, local process for nodes in an undirected graph to form...
research
∙
09/23/2022
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
This paper presents significantly improved deterministic algorithms for ...
research
∙
04/29/2022
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
This paper presents efficient distributed algorithms for a number of fun...
research
∙
04/18/2022
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
This paper presents new deterministic and distributed low-diameter decom...
research
∙
04/12/2022
Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel Distributed Algorithms
This paper presents near-optimal deterministic parallel and distributed ...
research
∙
11/02/2021
Fast Algorithms for Hop-Constrained Flows and Moving Cuts
Hop-constrained flows and their duals, moving cuts, are two fundamental ...
research
∙
10/29/2021
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
We provide universally-optimal distributed graph algorithms for (1+ε)-ap...
research
∙
04/08/2021
Universally-Optimal Distributed Algorithms for Known Topologies
Many distributed optimization algorithms achieve existentially-optimal r...
research
∙
02/09/2021
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Embeddings of graphs into distributions of trees that preserve distances...
research
∙
01/03/2021
Synchronization Strings and Codes for Insertions and Deletions – a Survey
Already in the 1960s, Levenshtein and others studied error-correcting co...
research
∙
11/20/2020
Hop-Constrained Oblivious Routing
We prove the existence of an oblivious routing scheme that is poly(log n...
research
∙
11/11/2020
Tree Embeddings for Hop-Constrained Network Design
Network design problems aim to compute low-cost structures such as route...
research
∙
09/28/2020
Rate-Distance Tradeoffs for List-Decodable Insertion-Deletion Codes
This paper presents general bounds on the highest achievable rate for li...
research
∙
08/07/2020
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
We prove that any n-node graph G with diameter D admits shortcuts with c...
research
∙
07/17/2020
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
This paper studies linear and affine error-correcting codes for correcti...
research
∙
12/31/2019
Near-Optimal Schedules for Simultaneous Multicasts
We study the store-and-forward packet routing problem for simultaneous m...
research
∙
09/24/2019
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
We give a complete answer to the following basic question: "What is the ...
research
∙
05/07/2019
Network Coding Gaps for Completion Times of Multiple Unicasts
Arguably the most common network communication problem is multiple-unica...
research
∙
10/28/2018
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
We introduce fast-decodable indexing schemes for edit distance which can...
research
∙
09/18/2018
Optimal strategies for patrolling fences
A classical multi-agent fence patrolling problem asks: What is the maxim...
research
∙
08/02/2018
Algorithms for Noisy Broadcast under Erasures
The noisy broadcast model was first studied in [Gallager, TranInf'88] wh...
research
∙
06/14/2018
A Computational Approach to Organizational Structure
An organizational structure defines how an organization arranges and man...
research
∙
05/17/2018
Coding for Interactive Communication with Small Memory and Applications to Robust Circuits
Classically, coding theory has been concerned with the problem of transm...
research
∙
05/10/2018
Erasure Correction for Noisy Radio Networks
The radio network model is a well-studied abstraction for modeling wirel...
research
∙
04/10/2018
Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions
This paper gives a communication-optimal document exchange protocol and ...
research
∙
03/08/2018
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Synchronization strings are recently introduced by Haeupler and Shahrasb...
research
∙
02/23/2018
Synchronization Strings: List Decoding for Insertions and Deletions
We study codes that are list-decodable under insertions and deletions. S...
research
∙
02/11/2018
Faster Distributed Shortest Path Approximations via Shortcuts
A long series of recent results and breakthroughs have led to faster and...
research
∙
01/18/2018
Minor Excluded Network Families Admit Fast Distributed Algorithms
Distributed network optimization algorithms, such as minimum spanning tr...
research
∙
01/16/2018
Round- and Message-Optimal Distributed Graph Algorithms
Distributed graph algorithms that separately optimize for either the num...
research
∙
01/16/2018
Round- and Message-Optimal Distributed Part-Wise Aggregation
Distributed graph algorithms that separately optimize for either the num...
research
∙
11/25/2017