Collision-based Testers are Optimal for Uniformity and Closeness

DOI10.4086/cjtcs.2019.001zbMath1441.62068arXiv1611.03579OpenAlexW4232667875MaRDI QIDQ5232537

Eric Price, Ilias Diakonikolas, John Peebles, Themis Gouleakis

Publication date: 12 September 2019

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.03579

zbMATH Keywords

goodness of fitsample complexitydistribution testing

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Parametric hypothesis testing (62F03)

Related Items (7)

Concentration of the collision estimator ⋮ Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences ⋮ The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution ⋮ On the Optimal Analysis of the Collision Probability Tester (an Exposition) ⋮ Normal approximation and fourth moment theorems for monochromatic triangles ⋮ Multinomial goodness-of-fit based on \(U\)-statistics: high-dimensional asymptotic and minimax optimality ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample

Cites Work

• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• Introduction to Property Testing
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Testing k-Modal Distributions: Optimal Algorithms via Reductions
• Unnamed Item

This page was built for publication: Collision-based Testers are Optimal for Uniformity and Closeness