research
∙
07/31/2023
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Algorithms with predictions incorporate machine learning predictions int...
share
research
∙
07/18/2023
A Unifying Framework for Differentially Private Sums under Continual Observation
We study the problem of maintaining a differentially private decaying su...
research
∙
07/07/2023
Differential Privacy for Clustering Under Continual Observation
We consider the problem of clustering privately a dataset in ℝ^d that un...
research
∙
06/17/2023
Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation
Differential privacy is the de-facto privacy standard in data analysis. ...
research
∙
04/28/2023
Faster Submodular Maximization for Several Classes of Matroids
The maximization of submodular functions have found widespread applicati...
research
∙
03/21/2023
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
In fully dynamic clustering problems, a clustering of a given data set i...
research
∙
03/04/2023
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Oblivious routing is a well-studied distributed paradigm that uses stati...
research
∙
02/23/2023
Time Complexity of Broadcast and Consensus for Randomized Oblivious Message Adversaries
Broadcast and consensus are most fundamental tasks in distributed comput...
research
∙
02/22/2023
Differentially Private Data Structures under Continual Observation for Histograms and Related Queries
Binary counting under continual observation is a well-studied fundamenta...
research
∙
02/12/2023
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...
research
∙
01/22/2023
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
We present an auction algorithm using multiplicative instead of constan...
research
∙
01/13/2023
Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters
Emerging reconfigurable datacenters allow to dynamically adjust the netw...
research
∙
01/04/2023
Dynamic Maintenance of Monotone Dynamic Programs and Applications
Dynamic programming (DP) is one of the fundamental paradigms in algorith...
research
∙
12/06/2022
Online Min-Max Paging
Motivated by fairness requirements in communication networks, we introdu...
research
∙
11/21/2022
Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
We study the broadcast problem on dynamic networks with n processes. The...
research
∙
11/18/2022
Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
Data dissemination is a fundamental task in distributed computing. This ...
research
∙
11/17/2022
Incremental Approximate Maximum Flow in m^1/2+o(1) update time
We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flo...
research
∙
11/09/2022
Almost Tight Error Bounds on Differentially Private Continual Counting
The first large-scale deployment of private federated learning uses diff...
research
∙
11/07/2022
The Augmentation-Speed Tradeoff for Consistent Network Updates
Emerging software-defined networking technologies enable more adaptive c...
research
∙
08/16/2022
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
A dynamic graph algorithm is a data structure that answers queries about...
research
∙
05/02/2022
Leximax Approximations and Representative Cohort Selection
Finding a representative cohort from a broad pool of candidates is a goa...
research
∙
02/23/2022
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
We study fine-grained error bounds for differentially private algorithms...
research
∙
01/17/2022
Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies
Reconfigurable optical topologies promise to improve the performance in ...
research
∙
12/14/2021
On fully dynamic constant-factor approximation algorithms for clustering problems
Clustering is an important task with applications in many fields of comp...
research
∙
09/02/2021
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
We study the problem of finding flows in undirected graphs so as to mini...
research
∙
08/10/2021
Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
Fully dynamic graph algorithms that achieve polylogarithmic or better ti...
research
∙
06/29/2021
Fully Dynamic Four-Vertex Subgraph Counting
This paper presents a comprehensive study of algorithms for maintaining ...
research
∙
06/28/2021
Differentially Private Algorithms for Graphs Under Continual Observation
Differentially private algorithms protect individuals in data analysis s...
research
∙
05/27/2021
On the Complexity of Weight-Dynamic Network Algorithms
While operating communication networks adaptively may improve utilizatio...
research
∙
04/15/2021
Symbolic Time and Space Tradeoffs for Probabilistic Verification
We present a faster symbolic algorithm for the following central problem...
research
∙
02/22/2021
Recent Advances in Fully Dynamic Graph Algorithms
In recent years, significant advances have been made in the design and a...
research
∙
01/13/2021
Practical Fully Dynamic Minimum Cut Algorithms
We present a practically efficient algorithm for maintaining a global mi...
research
∙
11/02/2020
Tight Bounds for Online Graph Partitioning
We consider the following online optimization problem. We are given a gr...
research
∙
11/02/2020
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
We give two fully dynamic algorithms that maintain a (1+ε)-approximation...
research
∙
10/30/2020
A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems
Over the last two decades, a significant line of work in theoretical alg...
research
∙
10/20/2020
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
research
∙
05/05/2020
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
research
∙
04/30/2020
Fully-Dynamic Coresets
With input sizes becoming massive, coresets—small yet representative sum...
research
∙
04/24/2020
Faster Parallel Multiterminal Cuts
We give an improved branch-and-bound solver for the multiterminal cut pr...
research
∙
04/21/2020
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
We give the first non-trivial fully dynamic probabilistic tree embedding...
research
∙
04/21/2020
Dynamic Maintanance of Low-Stretch Probabilistic Tree Embeddings with Applications
We give the first non-trivial fully dynamic probabilistic tree embedding...
research
∙
04/20/2020
Dynamic Matching Algorithms in Practice
In recent years, significant advances have been made in the design and a...
research
∙
03/05/2020
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles
Independent set is a fundamental problem in combinatorial optimization. ...
research
∙
02/25/2020
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
In the dynamic minimum set cover problem, a challenge is to minimize the...
research
∙
02/25/2020
An Improved Algorithm for Dynamic Set Cover
We consider the minimum set cover problem in a dynamic setting. Here, we...
research
∙
02/24/2020
Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
Graph coloring is a fundamental problem in computer science. We study th...
research
∙
02/17/2020
Finding All Global Minimum Cuts In Practice
We present a practically efficient algorithm that finds all global minim...
research
∙
02/03/2020
Faster Fully Dynamic Transitive Closure in Practice
The fully dynamic transitive closure problem asks to maintain reachabili...
research
∙
10/08/2019
Upper and Lower Bounds for Fully Retroactive Graph Problems
Classic dynamic data structure problems maintain a data structure subjec...
research
∙
09/25/2019
