Everyone is welcome to attend as Dr. Elena Grigorescu presents, Testing k-Monotonicity (The Rise and Fall of Boolean Functions)
Abstract:
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 http://eccc.hpi-web.de/resources/jsMath/fonts/cmsy10/alpha/120/char44.png that alternate between the values 0 and 1 at most k times on any ascending chain in http://eccc.hpi-web.de/resources/jsMath/fonts/cmsy10/alpha/120/char44.png. 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.
Joint work with Clement Canonne, Siyao Guo, Akash Kumar, Karl Wimmer
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 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.
