Strong lower bounds for approximating distribution support size and the distinct elements problem

DOI10.1137/070701649MaRDI QIDQ3575150zbMATH OpenOpenAlexFDO

Authors

Publication date 7 July 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/070701649

zbMATH Keywords

lower boundsapproximation algorithmsPoissonizationdistinct elements problemdistribution support size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Sample complexity of the distinct elements problem
• The Complexity of Approximating the Entropy
• Approximating entropy from sublinear samples
• Sampling algorithms: lower bounds and applications

Cited in

(19)

• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Testing distributions of huge objects
• Bounds from a card trick
• A lower bound on the complexity of testing grained distributions
• Testing probability distributions using conditional samples
• Testing monotone continuous distributions on high-dimensional real cubes
• On approximating the number of relevant variables in a function
• Sublinear algorithms for approximating string compressibility
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Proofs of proximity for distribution testing
• \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
• An automatic inequality prover and instance optimal identity testing
• Testing convexity of figures under the uniform distribution
• Invariance in property testing
• Recovering structured probability matrices
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Robust characterizations of \(k\)-wise independence over product spaces and related testing results
• The power and limitations of uniform samples in testing properties of figures
• Sample complexity of the distinct elements problem

This page was built for publication: Strong lower bounds for approximating distribution support size and the distinct elements problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575150)