research
∙
09/09/2023
A constant factor approximation for Nash social welfare with subadditive valuations
We present a constant-factor approximation algorithm for the Nash social...
share
research
∙
04/28/2023
Faster Submodular Maximization for Several Classes of Matroids
The maximization of submodular functions have found widespread applicati...
research
∙
11/07/2022
Approximating Nash Social Welfare by Matching and Local Search
For any ε>0, we give a simple, deterministic (6+ε)-approximation algorit...
research
∙
11/07/2022
Towards an Optimal Contention Resolution Scheme for Matchings
In this paper, we study contention resolution schemes for matchings. Giv...
research
∙
08/19/2022
Secretary Problems: The Power of a Single Sample
In this paper, we investigate two variants of the secretary problem. In ...
research
∙
06/01/2022
On the Hardness of Dominant Strategy Mechanism Design
We study the communication complexity of dominant strategy implementatio...
research
∙
04/11/2022
On complex roots of the independence polynomial
It is known from the work of Shearer (1985) (and also Scott and Sokal (2...
research
∙
11/14/2021
Cardinality constrained submodular maximization for random streams
We consider the problem of maximizing submodular functions in single-pas...
research
∙
07/29/2021
Fixed-Price Approximations in Bilateral Trade
We consider the bilateral trade problem, in which two agents trade a sin...
research
∙
03/18/2021
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
We present a 380-approximation algorithm for the Nash Social Welfare pro...
research
∙
01/06/2021
Estimating the Nash Social Welfare for coverage and other submodular valuations
We study the Nash Social Welfare problem: Given n agents with valuation ...
research
∙
02/21/2020
A polynomial lower bound on adaptive complexity of submodular maximization
In large-data applications, it is desirable to design algorithms with a ...
research
∙
02/10/2020
Submodular Maximization Through Barrier Functions
In this paper, we introduce a novel technique for constrained submodular...
research
∙
02/27/2019
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Algorithmic stability is a classical approach to understanding and analy...
research
∙
12/24/2018
Generalization Bounds for Uniformly Stable Algorithms
Uniform stability of a learning algorithm is a classical notion of algor...
research
∙
10/02/2018