On the complexity of estimating the effective support size

DOI10.1007/978-3-031-88946-2_13MaRDI QIDQ6877275zbMATH OpenFDO

Authors Oded Goldreich

Publication date 8 January 2026

Full work available at URL https://doi.org/10.1007/978-3-031-88946-2_13

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Cites work

• Distribution testing lower bounds via reductions from communication complexity
• Estimating the Effective Support Size in Constant Query Complexity
• Introduction to Property Testing
• On the learnability of discrete distributions
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Testing probability distributions underlying aggregated data
• The Complexity of Approximating the Entropy

Cited in

(1)

• Testing support size more efficiently than learning histograms

This page was built for publication: On the complexity of estimating the effective support size

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