Talks & Seminars
Title: Junta Correlation is Testable
Prof. Anindya De, University of Pennsylvania
Date & Time: January 8, 2020 11:00
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/.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback