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

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

• When: Wed 1 March 2023, at 1:00 pm (GMT+10)
• Speaker: Dr Clément Canonne (University of Sydney)
• Host: Dr Yadan Luo
• Zoom: https://uqz.zoom.us/j/82896549343

Zoom Recording