Abstract
Since the early days of property testing, the problem of monotonicity testing has been a central problem of study. Despite the simplicity of the problem, the question has led to a (still continuing) flurry of papers over the past two decades. A long standing open problem has been to determine the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids.
This talk is about the (almost) resolution of this question, by \sqrt{d} query "path testers". The path to these results is through a beautiful theory of "directed isoperimetry", showing that classic isoperimetric theorems on the Boolean hypercube extend to the directed setting. This fact is surprising, since directed graphs/random walks are often ill-behaved and rarely yield a nice theory. These directed theorems provide an analysis of directed random walks on product domains, which lead to optimal monotonicity testers.
I will present some of the main tools used in these results, and try to provide an intuitive explanation of directed isoperimetric theorems.