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

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