Optimal Algorithms for Testing Closeness of Discrete Distributions
From MaRDI portal
Publication:5384050
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
Characterization and structure theory of statistical distributions (62E10) Randomized algorithms (68W20)
Related Items (26)
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
This page was built for publication: Optimal Algorithms for Testing Closeness of Discrete Distributions