CSE 290A, Spring 2020: Lec 13, uniformity testing
C. Seshadhri · 91:35
This lecture develops the classic collision-based tester for whether an unknown distribution \(P\) on \([n]\) is uniform, showing why \(\sqrt{n}/\varepsilon^4\) samples suffice via a birthday-paradox \(\ell2\) estimat...