116 citations · 1.1k across the 89 of their papers we have counts for
9 papers · 1 filter
Testing -Modal Distributions: Optimal Algorithms via Reductions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio +2
We give highly efficient algorithms, and almost matching lower bounds, for a range of basic statistical problems that involve testing and estimating the L_1 distance between two k-…
On Optimal Multi-Dimensional Mechanism Design
Constantinos Daskalakis, S. Matthew Weinberg
We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constan…
A Constructive Approach to Reduced-Form Auctions with Applications to Multi-Item Mechanism Design
Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg
We provide a constructive proof of Border's theorem [Bor91, HR15a] and its generalization to reduced-form auctions with asymmetric bidders [Bor07, MV10, CKM13]. Given a reduced for…
Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
Constantinos Daskalakis, Sebastien Roch
We present an efficient phylogenetic reconstruction algorithm allowing insertions and deletions which provably achieves a sequence-length requirement (or sample complexity) growing…
Learning Poisson Binomial Distributions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
We consider a basic problem in unsupervised learning: learning an unknown \emph{Poisson Binomial Distribution}. A Poisson Binomial Distribution (PBD) over is the…
Learning -Modal Distributions via Testing
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
A -modal probability distribution over the discrete domain is one whose histogram has at most "peaks" and "valleys." Such distributions are natural generalizat…