research
∙
10/13/2022
Online Algorithms for the Santa Claus Problem
The Santa Claus problem is a fundamental problem in fair division: the g...
share
research
∙
03/24/2022
Improved Communication Complexity of Fault-Tolerant Consensus
Consensus is one of the most thoroughly studied problems in distributed ...
research
∙
02/26/2020
Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
research
∙
12/22/2019
Approximate Maximum Matching in Random Streams
In this paper, we study the problem of finding a maximum matching in the...
research
∙
11/29/2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertex-weighted directed graph G...
research
∙
09/08/2019
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
We present the first algorithm for maintaining a maximal independent set...
research
∙
11/09/2018
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
The k-cut problem asks, given a connected graph G and a positive integer...
research
∙
07/17/2018
