Computer Science/Discrete Mathematics Seminar I

Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over $\{0,1\}^n$, we are interested in the number of queries required to distinguish whether an unknown function is monotone or far from every monotone function. In this talk we discuss recent results on Boolean monotonicity testing and some related problems, focusing on the lower bound side. Based on joint works with Anindya De, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie.