Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

H. Chernoff · 1952

Earlier work this paper cites.

Probability inequalities for sums of bounded random variables

W. Hoeffding · 1963

Earlier work this paper cites.

Statistical Inference under Order Restrictions

R.E. Barlow, D.J. Bartholomew, J.M. Bremner, and H.D. Brunk · 1972

Earlier work this paper cites.

Nonparametric Density Estimation: The L 1 L_{1} View

L. Devroye and L. Györfi · 1985

Earlier work this paper cites.

Density Estimation

B. W. Silverman · 1986

Earlier work this paper cites.

On the computational complexity and geometry of the first-order theory of the reals

J. Renegar · 1992

Earlier work this paper cites.

On the computational complexity of approximating solutions for real algebraic formulae

J. Renegar · 1992

Earlier work this paper cites.

Multivariate Density Estimation: Theory, Practice and Visualization

D.W. Scott · 1992

Earlier work this paper cites.

On the learnability of discrete distributions

M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie · 1994

Earlier work this paper cites.

An Introduction to Computational Learning Theory

M. Kearns and U. Vazirani · 1994

Earlier work this paper cites.

Statistical applications of the Poisson-Binomial and Conditional Bernoulli Distributions

S.X. Chen and J.S. Liu · 1997

Earlier work this paper cites.

Estimating a mixture of two product distributions

Y. Freund and Y. Mansour · 1999

Earlier work this paper cites.

Learning mixtures of arbitrary Gaussians

S. Arora and R. Kannan · 2001

Earlier work this paper cites.

Combinatorial methods in density estimation

L. Devroye and G. Lugosi · 2001

Earlier work this paper cites.

Evolutionary trees can be learned in polynomial time in the two state general Markov model

M. Cryan, L. Goldberg, and P. Goldberg · 2002

Earlier work this paper cites.

A spectral algorithm for learning mixtures of distributions

S. Vempala and G. Wang · 2002

Earlier work this paper cites.

Learning mixtures of product distributions over discrete domains

J. Feldman, R. O’Donnell, and R. Servedio · 2005

Earlier work this paper cites.

Computing equilibria in anonymous games

C. Daskalakis and C. H. Papadimitriou · 2007

Earlier work this paper cites.

On Oblivious PTAS’s for Nash Equilibrium

C. Daskalakis and C. Papadimitriou · 2009

Cited alongside, same era.

Concentration of measure for the analysis of randomized algorithms

D. Dubhashi and A. Panconesi · 2009

Cited alongside, same era.

Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency

L. D umbgen and K. Rufibach · 2009

Cited alongside, same era.

On the rate of convergence of the maximum likelihood estimator of a k k -monotone density

F. Gao and J. A. Wellner · 2009

Cited alongside, same era.

Inference and modeling with log-concave distributions

G. Walther · 2009

Cited alongside, same era.

Polynomial learning of distribution families

M. Belkin and K. Sinha · 2010

Cited alongside, same era.

Faster and sample near-optimal algorithms for proper learning mixtures of gaussians

C. Daskalakis and G. Kamath · 2014

Later among the works it cites.

Sparse covers for sums of indicators

C. Daskalakis and C. Papadimitriou · 2014

Later among the works it cites.

Approximate nash equilibria in anonymous games

C. Daskalakis and C. H. Papadimitriou · 2014

Later among the works it cites.

Query complexity of approximate equilibria in anonymous games

Original

P. W. Goldberg and S. Turchetta · 2014

Later among the works it cites.

Global rates of convergence in log-concave density estimation

Original

A. K. H. Kim and R. J. Samworth · 2014

Later among the works it cites.

Near-optimal-sample estimators for spherical gaussian mixtures