On the Optimal Analysis of the Collision Probability Tester (an Exposition)

DOI10.1007/978-3-030-43662-9_16OpenAlexW3014256000MaRDI QIDQ5098781

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_16

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Property testing and its connection to learning and approximation
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• 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

This page was built for publication: On the Optimal Analysis of the Collision Probability Tester (an Exposition)