Testing support size more efficiently than learning histograms

DOI10.46298/THEORETICS.26.10MaRDI QIDQ7254605zbMATH OpenFDO

Authors Pinto Jr. Renato Ferreira, Nathaniel Harms

Publication date 28 May 2026

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.26.10

zbMATH Keywords

Chebyshev polynomialsdistribution testingproperty testingsupport size

Mathematics Subject Classification ID

Theory of computing (68Qxx) Artificial intelligence (68Txx) Algorithms in computer science (68Wxx)

Cites work

• Distribution testing lower bounds via reductions from communication complexity
• Introduction to Property Testing
• Learnability and the Vapnik-Chervonenkis dimension
• On sample-based testers
• On the complexity of estimating the effective support size
• On the Estimation of the Number of Classes in a Population
• On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
• Property testing and its connection to learning and approximation
• Refining the adaptivity notion in the huge object model
• Support testing in the huge object model
• Testing distributions of huge objects
• The optimal sample complexity of PAC learning
• THE POPULATION FREQUENCIES OF SPECIES AND THE ESTIMATION OF POPULATION PARAMETERS
• VC dimension and distribution-free sample-based testing

This page was built for publication: Testing support size more efficiently than learning histograms

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