Estimating the unseen

DOI10.1145/1993636.1993727zbMath1288.68186OpenAlexW2127090196MaRDI QIDQ5419139

Paul Valiant, Gregory Valiant

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993727

zbMATH Keywords

entropyStein's methodcentral limit theoremlower boundssupport sizedistinct elements problemproperty estimation

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Nonparametric estimation (62G05) Central limit and other weak theorems (60F05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Statistical aspects of information-theoretic topics (62B10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (29)

Hypothesis testing for high-dimensional multinomials: a selective review ⋮ Unnamed Item ⋮ Bounds on the Poincaré constant for convolution measures ⋮ A high-dimensional CLT in \(\mathcal {W}_2\) distance with near optimal convergence rate ⋮ On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition) ⋮ The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution ⋮ Optimal Estimation of Wasserstein Distance on a Tree With an Application to Microbiome Studies ⋮ Unnamed Item ⋮ Bounds from a card trick ⋮ Unnamed Item ⋮ Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting) ⋮ Testing shape restrictions of discrete distributions ⋮ On the Power of Statistical Zero Knowledge ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ The CLT in high dimensions: quantitative bounds via martingale embedding ⋮ Recovering Structured Probability Matrices ⋮ Proofs of Proximity for Distribution Testing ⋮ Chebyshev polynomials, moment matching, and optimal estimation of the unseen ⋮ Quantum spectrum testing ⋮ A simple method for estimating the entropy of neural activity ⋮ Sample complexity of the distinct elements problem ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Serving content with unknown demand: the high-dimensional regime ⋮ Simple and efficient pseudorandom generators from gaussian processes ⋮ Estimating graph parameters with random walks ⋮ Unnamed Item ⋮ Testing Probability Distributions using Conditional Samples ⋮ Learning Poisson binomial distributions ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample

This page was built for publication: Estimating the unseen