A lower bound on the complexity of testing grained distributions

DOI10.1007/s00037-023-00245-wOpenAlexW3202762636MaRDI QIDQ6063025

Dana Ron, Oded Goldreich

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

• Property testing and its connection to learning and approximation
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• Estimating the Unseen
• Advanced Linear Algebra
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• Introduction to Property Testing
• Testing Closeness of Discrete Distributions

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