Please note: This PhD seminar will be given online
Amit
Levi, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
Given a distribution p supported on {-1,1}^n, we want to test whether p is uniform or ϵ-far from uniform in total variation distance. The fact that p is a high dimensional distribution is inconsequential for the sample complexity, which is well-known to be Θ(2^{n/2} / ε^2). To benefit from the high dimensional structure, we study the subcube conditional sampling model, first considered in Bhattacharyya and Chakraborty (2018), and give a nearly optimal algorithm for testing uniformity on {-1,1}^n making Õ(√n/ ε^2) queries. The key ingredient is a natural notion of random restriction for distributions on {-1,1}^n, and an inequality describing the behaviour of the mean vector after a random restriction.
To join this PhD seminar on Zoom, please go to https://zoom.us/j/99723663216