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

DOI10.1137/070701649zbMATH Open1194.68124OpenAlexW2170990775MaRDI QIDQ3575150FDOQ3575150

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

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

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)

Cited In (19)

• Testing distributions of huge objects
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• 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
• Testing convexity of figures under the uniform distribution
• An automatic inequality prover and instance optimal identity testing
• 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)