The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution

DOI10.1007/978-3-030-43662-9_10MaRDI QIDQ5098775zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43662-9_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Testing identity of structured distributions
• Sample-optimal identity testing with high probability
• Distributed uniformity testing
• Testing k-modal distributions: optimal algorithms via reductions
• Distribution testing lower bounds via reductions from communication complexity

Cites work

• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• An automatic inequality prover and instance optimal identity testing
• Collision-based Testers are Optimal for Uniformity and Closeness
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Instance Optimal Distribution Testing and Learning
• Introduction to Property Testing
• On testing expansion in bounded-degree graphs
• On the Optimal Analysis of the Collision Probability Tester (an Exposition)
• On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
• Optimal algorithms for testing closeness of discrete distributions
• Property testing and its connection to learning and approximation
• Testing identity of structured distributions
• Tolerant property testing and distance approximation

Cited in

(8)

• Can Distributed Uniformity Testing Be Local?
• Collision-based Testers are Optimal for Uniformity and Closeness
• Testing Data Binnings
• A lower bound on the complexity of testing grained distributions
• Geometric reduction for identity testing of reversible Markov chains
• Distribution-free proofs of proximity
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Comparison graphs: a unified method for uniformity testing

This page was built for publication: The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098775)