Near-Optimal Bounds for Testing Histogram Distributions

Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Sihan Liu

Type: Preprint

Publication Date: 2022-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.2207.06596

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Near-Optimal Closeness Testing of Discrete Histogram Distributions	2017	Ilias Diakonikolas Daniel M. Kane Vladimir Nikishkin
+	Near-Optimal Closeness Testing of Discrete Histogram Distributions	2017	Ilias Diakonikolas Daniel M. Kane Vladimir Nikishkin
+	Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms	2014	Siu-On Chan Ilias Diakonikolas Rocco A. Servedio Xiaorui Sun
+	Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms	2014	Siu On Chan Ilias Diakonikolas Rocco A. Servedio Xiaorui Sun
+ PDF Chat	Testing Support Size More Efficiently Than Learning Histograms	2024	Renato Ferreira Pinto Nathaniel Harms
+ PDF Chat	Efficient density estimation via piecewise polynomial approximation	2014	Siu-On Chan Ilias Diakonikolas Rocco A. Servedio Xiaorui Sun
+	Sample-Optimal Density Estimation in Nearly-Linear Time	2015	Jayadev Acharya Ilias Diakonikolas Jerry Li Ludwig Schmidt
+	Testing Identity of Multidimensional Histograms	2018	Ilias Diakonikolas Daniel M. Kane John Peebles
+	Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms	2018	Ilias Diakonikolas Jerry Li Ludwig Schmidt
+	Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms	2018	Ilias Diakonikolas Jerry Li Ludwig Schmidt
+	Testing $k$-Modal Distributions: Optimal Algorithms via Reductions	2011	Constantinos Daskalakis Ilias Diakonikolas Rocco A. Servedio Gregory Valiant Paul Valiant
+ PDF Chat	Statistical-Computational Trade-offs for Density Estimation	2024	Anders Aamand Alexandr Andoni Justin Y. Chen Piotr Indyk Shyam Narayanan Sandeep Silwal Haike Xu
+	Estimating Entropy of Distributions in Constant Space	2019	Jayadev Acharya Sourbh Bhadane Piotr Indyk Ziteng Sun
+	Which Distribution Distances are Sublinearly Testable?	2017	Constantinos Daskalakis Gautam Kamath John C. Wright
+	Sample-Optimal Density Estimation in Nearly-Linear Time	2017	Jayadev Acharya Ilias Diakonikolas Jerry Li Ludwig Schmidt
+	Which Distribution Distances are Sublinearly Testable	2017	Constantinos Daskalakis Gautam Kamath John C. Wright
+	Optimal Testing of Discrete Distributions with High Probability	2020	Ilias Diakonikolas Themis Gouleakis Daniel M. Kane John Peebles Eric Price
+	Optimal Testing of Discrete Distributions with High Probability	2020	Ilias Diakonikolas Themis Gouleakis Daniel M. Kane John Peebles Eric Price
+	Streaming Algorithms for Support-Aware Histograms	2022	Justin Y. Chen Piotr Indyk Tal Wagner
+	Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions	2015	Ilias Diakonikolas Daniel M. Kane Vladimir Nikishkin

Works That Cite This (1)

Action	Title	Year	Authors
+	Testing Closeness of Multivariate Distributions via Ramsey Theory	2024	Ilias Diakonikolas D. Kane Sihan Liu

Works Cited by This (0)

Action	Title	Year	Authors