Room 327

Testing Distributions for Uniformity

Vinodchandran Variyam

University of Nebraska, Lincoln

Given samples from a fixed but unknown distribution D over a
discrete domain, we would like to decide whether D satisfies certain
property P or not. An important instance of this distribution property
testing problem is the uniformity testing problem: testing whether the
unknown distribution D is close to the uniform distribution or not, in
total variation distance. The main resource to be minimized is the
number of samples drawn from the unknown distribution D. In recent
years there has been a surge in the interest in this area, due to its
importance in data analytics.

In this talk we mostly focus on the uniformity testing problem. After
a short survey of results, we will present a new and simple analysis
of a known uniformity tester that achieves the strongest known
guarantee. This is a joint work with A. Pavan and Sutanu Gayen.