The Long Path to Square Root of d Monotonicity Testers

Explore a comprehensive lecture on the evolution and resolution of monotonicity testing for Boolean functions on hypergrids. Delve into the concept of "path testers" with \sqrt{d} query complexity, which nearly solves a long-standing open problem in property testing. Discover the fascinating theory of "directed isoperimetry" and its surprising extension of classic isoperimetric theorems to the directed setting on the Boolean hypercube. Examine how these directed theorems enable the analysis of directed random walks on product domains, leading to optimal monotonicity testers. Gain insights into the main tools employed in these results and grasp an intuitive understanding of directed isoperimetric theorems. Learn from C. Seshadhri of UC Santa Cruz as part of the Workshop on Local Algorithms (WoLA) at the Simons Institute, in this 56-minute talk that bridges decades of research in this fundamental area of computer science.

The long path to \sqrt{d} monotonicity testers