Speaker: Elena Grigorescu, Purdue University
Title: Testing k-Monotonicity (The Rise and Fall of Boolean Functions)
Host: Mariana Raykova
Boolean functions are commonly used to represent a diverse set of objects: voting schemes, graphs, error-correcting codes or concept classes. Therefore, their study is of interest to multiple communities, both from theoretical and practical angles.
In this talk I will introduce Boolean k-monotone functions, which are functions defined over a finite poset domain D that alternate between the values 0 and 1 at most k times on any ascending chain in D. Hence, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions.
This work is motivated by the recent interest in k-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing. Here we initiate a systematic study of k-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are k-monotone (or are close to being k-monotone) from functions that are far from being k-monotone.
I will present several results for testing k-monotonicity on the hypercube and hypergrid domains, outline some connections with distribution testing and with some learning problems, and discuss a few important open questions.
Bio: Elena Grigorescu is an Assistant Professor in the Computer Science Department of Purdue University. She graduated from EECS MIT in 2010, and after that she spent two years as a Computing Innovations postdoctoral fellow at Georgia Tech. Her research interests span many aspects of theoretical Computer Science, with a focus on sublinear algorithms, error-correcting codes and point lattices, and complexity theory.