ABSTRACT

Given access to a distribution, how can one tell whether it satisfies a particular property? This talk will be about property testing of distributions, which studies the above question from an algorithmic perspective. We will see how, for distributions over high-dimensional domains, property testing becomes much harder—with exponential dependencies on the dimension—and we will explore approaches to overcome this “curse of dimensionality.” In particular, we will talk about the subcube conditional sampling model, and how, for many properties of distributions over {-1,1}^d, we can achieve polynomial-in-dimension running times.

BIO

Erik Waingarten is an assistant professor in the Computer and Information Sciences department at the University of Pennsylvania. His research is in algorithms for massive datasets, with a focus on similarity search, streaming/sketching, property testing, and distribution testing.