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

DOI10.1007/978-3-030-43662-9_10OpenAlexW2578286516MaRDI QIDQ5098775

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)

Related Items (4)

Collision-based Testers are Optimal for Uniformity and Closeness ⋮ A lower bound on the complexity of testing grained distributions ⋮ Geometric reduction for identity testing of reversible Markov chains ⋮ Testing Data Binnings

Cites Work

• Tolerant property testing and distance approximation
• An Automatic Inequality Prover and Instance Optimal Identity Testing
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• Instance Optimal Distribution Testing and Learning
• On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
• On the Optimal Analysis of the Collision Probability Tester (an Exposition)
• Collision-based Testers are Optimal for Uniformity and Closeness
• Testing Identity of Structured Distributions
• Introduction to Property Testing
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Estimating the unseen

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