CS Talk - Elena Grigorescu

Event time: 
Thursday, October 13, 2016 - 10:30am
Location: 
AKW 400 See map
51 Prospect Street
New Haven, CT 06511
Event description: 

Speaker: Elena Grigorescu, Purdue University
Title: Testing k-Monotonicity (The Rise and Fall of Boolean Functions)

Host: Mariana Raykova

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 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.

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 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.