Estimating the unseen: A sublinear-sample canonical estimator of distributions

By Gregory Valiant, Paul Valiant. 2010

39 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Paul Valiant
2. Gregory Valiant
3. Joseph Bonneau
4. Jiantao Jiao
5. Jayadev Acharya
6. Ananda Theertha Suresh
7. Sivaraman Balakrishnan
8. Yihong Wu

Citations in the corpus

• Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (2011, background): “We leverage this central limit theorem to prove a stronger but more speci.c central limit theorem for generalized multinomial distributions a large class of discrete distributions, parameterized by matri­ * Preliminary full versions, [39] and [40], available at:…”
• A CLT and tight lower bounds for estimating entropy (2010, background): “We explicitly exhibit such a family of pairs of distributions D,D′ via a Laguerre polynomial construction that may be of independent interest.”
• Guessing human-chosen secrets (2012, background): “In 2011 Valiant and Valiant proved an optimal algorithm for determining H1 to within an additive constant requiring O ( N lnN ) samples [298].”