Time: Wednesday, 08 January 2020, 11:00am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
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/.
Organization:
University of Pennsylvania
Host:
Prof. Nutan Limaye
User:
Department Calendar
Send Reminder:
Yes - 182 hours 51 minutes before start
Description:
Speaker: Kiran Shiragur
Time: Wednesday, 08 January 2020, 2:00pm
Venue: CC 109
Abstract:
Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single estimator that maximizes profile maximum likelihood (PML) is sample competitive for all symmetric properties. Further, they showed that even a 2^{n^{1-delta}}-approximate maximizer of the PML objective can serve as such a universal plug-in estimator. (Here n is the size of the sample). Unfortunately, no polynomial time computable PML estimator with such an approximation guarantee was known. We provide the first such estimator and show how to compute it in time nearly linear in n. The PML objective is related to the permanent of a certain Vandermonde matrix. A surprising connection between the convex relaxation we introduce and the Bethe free energy approximation originating in statistical physics leads to new bounds on the Bethe permanent of non-negative matrices.
This is in joint work with Moses Charikar and Aaron Sidford
Speaker Profile:
Kiran Shiragur is a PhD student at Stanford university. His area of research is operations research and theoretical computer science.