Optimal Algorithms for Testing Closeness of Discrete Distributions

DOI10.1137/1.9781611973402.88zbMath1421.68184arXiv1308.3946OpenAlexW2952058015MaRDI QIDQ5384050

Siu-On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Characterization and structure theory of statistical distributions (62E10) Randomized algorithms (68W20)

Related Items

Minimax optimality of permutation tests, Hypothesis testing for high-dimensional multinomials: a selective review, Local minimax rates for closeness testing of discrete distributions, Collision-based Testers are Optimal for Uniformity and Closeness, Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences, Analysis of COVID-19 evolution based on testing closeness of sequential data, Optimal Identity Testing with High Probability, 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), Unnamed Item, Anonymous whistleblowing over authenticated channels, Testing shape restrictions of discrete distributions, An Automatic Inequality Prover and Instance Optimal Identity Testing, Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs, On the power of conditional samples in distribution testing, Recovering Structured Probability Matrices, Proofs of Proximity for Distribution Testing, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Two Party Distribution Testing: Communication and Security, Quantum Chebyshev's Inequality and Applications, Unnamed Item, Optimal Stopping Rules for Sequential Hypothesis Testing, Communication Complexity of Statistical Distance, Testing Probability Distributions using Conditional Samples, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Topics and Techniques in Distribution Testing: A Biased but Representative Sample