university of sydney,

No.23-02 Seven Algorithms for the Same Task (Testing Uniformity)

Yadan Luo Follow Mar 08, 2023 · 1 min read
No.23-02 Seven Algorithms for the Same Task (Testing Uniformity)
Share this

Suppose you get a set of (independent) data points in some discrete but huge domain {1,2,…,k}, and want to determine if this data is uniformly distributed. This is a basic and fundamental problem in Statistics, and has applications in computer science, not all made up: from testing the mixing time of a random walk, to detecting malicious changes in a data stream, to selecting a good algorithm depending on the input distribution.

The goal, of course, is to perform this task efficiently, both time- (time complexity) and data-wise (sample complexity). In this talk, I will survey and discuss seven algorithms for uniformity testing, and explain some of their (dis)advantages.

Short Bio

Clément Canonne is a Lecturer in the School of Computer Science of the University of Sydney, and an ARC DECRA fellow; he obtained his Ph.D. in 2017 from Columbia University, before joining Stanford as a Motwani Postdoctoral Fellow, then IBM Research as a Goldstine Postdoctoral Fellow. His main areas of research are distribution testing (and, broadly speaking, property testing) and learning theory; focusing, in particular, on understanding the computational aspects of learning and statistical inference subject to various resource or information constraints.

More Details

Zoom Recording

Join Newsletter
Get the latest news right in your inbox. We never spam!