research
∙
10/06/2022
The Power of Greedy for Online Minimum Cost Matching on the Line
We consider the online minimum cost matching problem on the line, in whi...
share
research
∙
09/08/2022
Strategyproof Scheduling with Predictions
In their seminal paper that initiated the field of algorithmic mechanism...
research
∙
05/02/2022
Scheduling with Speed Predictions
Algorithms with predictions is a recent framework that has been used to ...
research
∙
04/03/2022
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
In this work we introduce an alternative model for the design and analys...
research
∙
02/21/2022
Learning Low Degree Hypergraphs
We study the problem of learning a hypergraph via edge detecting queries...
research
∙
07/20/2021
Deterministic Budget-Feasible Clock Auctions
We revisit the well-studied problem of budget-feasible procurement, wher...
research
∙
02/23/2021
Instance Specific Approximations for Submodular Maximization
For many optimization problems in machine learning, finding an optimal s...
research
∙
10/22/2020
Adversarial Attacks on Binary Image Recognition Systems
We initiate the study of adversarial attacks on models for binary (i.e. ...
research
∙
07/14/2019
The FAST Algorithm for Submodular Maximization
In this paper we describe a new algorithm called Fast Adaptive Sequencin...
research
∙
06/07/2019
Dynamic First Price Auctions Robust to Heterogeneous Buyers
We study dynamic mechanisms for optimizing revenue in repeated auctions,...
research
∙
11/15/2018
Secretary Ranking with Minimal Inversions
We study a twist on the classic secretary problem, which we term the sec...
research
∙
11/07/2018
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
In this paper we study submodular maximization under a matroid constrain...
research
∙
08/12/2018
Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
In this paper we study the limitations of parallelization in convex opti...
research
∙
07/30/2018
Non-monotone Submodular Maximization in Exponentially Fewer Iterations
In this paper we consider parallelization for applications whose objecti...
research
∙
05/09/2018
On the Construction of Substitutes
Gross substitutability is a central concept in Economics and is connecte...
research
∙
04/17/2018
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
In this paper we study the adaptivity of submodular maximization. Adapti...
research
∙
01/23/2018