research
∙
01/17/2023
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
The packet routing problem asks to select routing paths that minimize th...
share
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
∙
05/30/2022
Universally-Optimal Distributed Exact Min-Cut
We present a universally-optimal distributed algorithm for the exact wei...
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
∙
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
∙
10/22/2021
A Simple Boosting Framework for Transshipment
Transshipment, also known under the names of earth mover's distance, unc...
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
∙
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
∙
10/16/2020
Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
We address the challenge of finding algorithms for online allocation (i....
research
∙
11/17/2019
Robust Algorithms for the Secretary Problem
In classical secretary problems, a sequence of n elements arrive in a un...
research
∙
05/07/2019
Network Coding Gaps for Completion Times of Multiple Unicasts
Arguably the most common network communication problem is multiple-unica...
research
∙
02/04/2019
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Consider a kidney-exchange application where we want to find a max-match...
research
∙
05/10/2018
Erasure Correction for Noisy Radio Networks
The radio network model is a well-studied abstraction for modeling wirel...
research
∙
01/18/2018