research
∙
08/20/2023
Improved Differentially Private Densest Subgraph: Local and Purely Additive
We study the Densest Subgraph problem under the additional constraint of...
share
research
∙
08/09/2023
Controlling Tail Risk in Online Ski-Rental
The classical ski-rental problem admits a textbook 2-competitive determi...
research
∙
04/13/2023
Improved Approximations for Relative Survivable Network Design
One of the most important and well-studied settings for network design i...
research
∙
02/22/2023
Degrees and Network Design: New Problems and Approximations
While much of network design focuses mostly on cost (number or weight of...
research
∙
10/22/2022
Algorithms with Prediction Portfolios
The research area of algorithms with predictions has seen recent success...
research
∙
09/08/2022
Epic Fail: Emulators can tolerate polynomially many edge faults for free
A t-emulator of a graph G is a graph H that approximates its pairwise sh...
research
∙
08/11/2022
Smoothed Analysis of Information Spreading in Dynamic Networks
The best known solutions for k-message broadcast in dynamic networks of ...
research
∙
06/24/2022
Relative Survivable Network Design
One of the most important and well-studied settings for network design i...
research
∙
02/16/2022
Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
The spread of an epidemic is often modeled by an SIR random process on a...
research
∙
09/16/2021
Vertex Fault-Tolerant Emulators
A k-spanner of a graph G is a sparse subgraph that preserves its shortes...
research
∙
07/20/2021
Faster Matchings via Learned Duals
A recent line of research investigates how algorithms can be augmented w...
research
∙
06/09/2021
Fair Disaster Containment via Graph-Cut Problems
Graph cut problems form a fundamental problem type in combinatorial opti...
research
∙
02/22/2021
Partially Optimal Edge Fault-Tolerant Spanners
Recent work has established that, for every positive integer k, every n-...
research
∙
07/16/2020
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Recent work has pinned down the existentially optimal size bounds for ve...
research
∙
02/25/2020
Efficient and Simple Algorithms for Fault Tolerant Spanners
It was recently shown that a version of the greedy algorithm gives a con...
research
∙
01/21/2020
Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
New optical technologies offer the ability to reconfigure network topolo...
research
∙
08/05/2019
The Capacity of Smartphone Peer-to-Peer Networks
We study three capacity problems in the mobile telephone model, a networ...
research
∙
05/17/2019
Lasserre Integrality Gaps for Graph Spanners and Related Problems
There has been significant recent progress on algorithms for approximati...
research
∙
03/18/2019
The Norms of Graph Spanners
A t-spanner of a graph G is a subgraph H in which all distances are pres...
research
∙
11/09/2018
Policy Regret in Repeated Games
The notion of policy regret in online learning is a well defined? perfor...
research
∙
10/21/2018
Distributed Approximate Distance Oracles
Data structures that allow efficient distance estimation (distance oracl...
research
∙
06/08/2018
Distributed Algorithms for Minimum Degree Spanning Trees
The minimum degree spanning tree (MDST) problem requires the constructio...
research
∙
02/28/2018