Estimating the unseen

DOI10.1145/1993636.1993727zbMath1288.68186MaRDI QIDQ5419139

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

entropy; Stein's method; central limit theorem; lower bounds; support size; distinct elements problem; property estimation

Mathematics Subject Classification ID

62H12: Estimation in multivariate analysis

62G05: Nonparametric estimation

60F05: Central limit and other weak theorems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

62B10: Statistical aspects of information-theoretic topics

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

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