Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
From MaRDI portal
Publication:3575150
DOI10.1137/070701649zbMath1194.68124OpenAlexW2170990775MaRDI QIDQ3575150
No author found.
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
lower boundsapproximation algorithmsPoissonizationdistinct elements problemdistribution support size
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (18)
Sublinear algorithms for approximating string compressibility ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ A lower bound on the complexity of testing grained distributions ⋮ Bounds from a card trick ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ Testing convexity of figures under the uniform distribution ⋮ On the power of conditional samples in distribution testing ⋮ Recovering Structured Probability Matrices ⋮ Proofs of Proximity for Distribution Testing ⋮ Chebyshev polynomials, moment matching, and optimal estimation of the unseen ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Sample complexity of the distinct elements problem ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Invariance in Property Testing ⋮ Testing Monotone Continuous Distributions on High-Dimensional Real Cubes ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ Testing Probability Distributions using Conditional Samples
This page was built for publication: Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
