research
∙
01/28/2023
Supergeo Design: Generalized Matching for Geographic Experiments
We propose a generalization of the standard matched pairs design in whic...
share
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
∙
05/05/2019
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
research
∙
11/30/2018
Fast Algorithms for Knapsack via Convolution and Prediction
The knapsack problem is a fundamental problem in combinatorial optimizat...
research
∙
11/20/2018
A general framework for handling commitment in online throughput maximization
We study a fundamental online job admission problem where jobs with dead...
research
∙
09/13/2018
Submodular Secretary Problem with Shortlists
In , the goal is to select k items in a randomly ordered input so as to ...
research
∙
11/17/2017
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
We present a simple randomized reduction from fully-dynamic integral mat...
research
∙
11/08/2017