ICTS:31839

Video URL

The long path to \sqrt{d} monotonicity testers

The long path to \sqrt{d} monotonicity testers

(2025). The long path to \sqrt{d} monotonicity testers. SciVideos. https://youtube.com/live/vylMwX7QkqE

The long path to \sqrt{d} monotonicity testers. SciVideos, May. 12, 2025, https://youtube.com/live/vylMwX7QkqE 

          @misc{ scivideos_ICTS:31839,
            doi = {},
            url = {https://youtube.com/live/vylMwX7QkqE},
            author = {},
            keywords = {},
            language = {en},
            title = {The long path to \sqrt{d} monotonicity testers},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31839 see, \url{https://scivideos.org/icts-tifr/31839}}
          }
C. Seshadhri
Talk numberICTS:31839
Source RepositoryICTS-TIFR

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.