research
∙
01/17/2023
Subset Sum in Time 2^n/2 / poly(n)
A major goal in the area of exact exponential algorithms is to give an a...
share
research
∙
07/10/2022
The Price of Stability for First Price Auction
This paper establishes the Price of Stability (PoS) for First Price Auct...
research
∙
07/05/2022
First Price Auction is 1 - 1/e^2 Efficient
We prove that the PoA of First Price Auctions is 1 - 1/e^2 ≈ 0.8647, clo...
research
∙
10/27/2021
Average-Case Subset Balancing Problems
Given a set of n input integers, the Equal Subset Sum problem asks us to...
research
∙
07/22/2021
Fourier growth of structured 𝔽_2-polynomials and applications
We analyze the Fourier growth, i.e. the L_1 Fourier weight at level k (d...
research
∙
02/15/2021
Tight Revenue Gaps among Multi-Unit Mechanisms
This paper considers Bayesian revenue maximization in the k-unit setting...
research
∙
05/13/2020
A robust multi-dimensional sparse Fourier transform in the continuous setting
Sparse Fourier transform (Sparse FT) is the problem of learning an unkno...
research
∙
12/20/2019
Learning Reserve Prices in Second-Price Auctions
This paper proves the tight sample complexity of Second-Price Auction w...
research
∙
02/12/2019
Optimal Budget-Feasible Mechanisms for Additive Valuations
In this paper, we obtain tight approximation guarantee for budget-feasib...
research
∙
02/07/2019
On Asymptotically Tight Tail Bounds for Sums of Geometric and Exponential Random Variables
In this note we prove bounds on the upper and lower probability tails of...
research
∙
11/02/2018
Tight Approximation Ratio of Anonymous Pricing
We consider two canonical Bayesian mechanism design settings. In the sin...
research
∙
04/02/2018