Title: Junta Correlation is Testable

Description: Speaker: Prof. Anindya De

Time: Wednesday, 08 January 2020, 11:00am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building

A Boolean function f on the n-dimensional hypercube is said to be a k-junta if it is dependent only on some k coordinates of the input. These functions have been widely studied in the context of PCPs, learning theory and property testing. In particular, a flagship result in property testing is that k-juntas can be tested with \tilde{O}(k) queries -- i.e., there is an algorithm which when given a black box to f, makes only \tilde{O}(k) queries and decides between the following two cases:
1. f is a k-junta.
2. f is at least 0.01 far from every k-junta g in Hamming distance.

Surprisingly, the query complexity is completely independent of the ambient dimension n. In this work, we achieve the same qualitative guarantee for the noise tolerant version of this problem. In particular, we give a 2^k query algorithm to distinguish between the following two cases.
1. f is 0.48-close to some k-junta.
2. f is at least 0.49 far from every k-junta.

The algorithm and its proof of correctness are simple and modular employing some classical tools like “random restrictions” with elementary properties of the noise operator on the cube.

Joint work with Elchanan Mossel and Joe Neeman.

Speaker Profile:
Dr. Anindya De is an Assistant Professor in the Dept. of Computer and Information Science at University of Pennsylvania. More details about him are available at https://www.seas.upenn.edu/~anindyad/.

University of Pennsylvania

Prof. Nutan Limaye

Date: Wednesday, 8 January, 2020
Time: 11:00am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Monday, 11 January, 2021 7:20am IST
Send Reminder: Yes  -  119 hours 30 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)