On the query complexity of Boolean monotonicity testing

 Computer Science/Discrete Mathematics Seminar I Topic: On the query complexity of Boolean monotonicity testing Speaker: Xi Chen Affiliation: Columbia University Date: Monday, October 24 Time/Room: 11:15am - 12:15pm/S-101 Video Link: https://video.ias.edu/csdm/20161024-XiChen

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.