A lower bound on the complexity of testing grained distributions

DOI10.1007/S00037-023-00245-WMaRDI QIDQ6063025zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 2 December 2023

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-023-00245-w

zbMATH Keywords

distributionsproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Advanced Linear Algebra
• Estimating the unseen, improved estimators for entropy and other properties
• Introduction to Property Testing
• Property testing and its connection to learning and approximation
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Testing closeness of discrete distributions
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution

Cited in

(2)

• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Testing distributions of huge objects

This page was built for publication: A lower bound on the complexity of testing grained distributions

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