TCS+ Talk
Abstract: Joint Work with Vishnu Iyer and Michael Whitmeyer
A Boolean function $f:{0,1}^n \to {0,1}$ is called a k-junta if it depends only on k out of the n input bits. Junta testing is the task of distinguishing between k-juntas and functions that are far from k-juntas. A long line of work settled the query complexity of testing k-juntas, which is O(k log(k)) [Blais, STOC 2009; Saglam, FOCS 2018]. Suppose, however, that f is not a perfect k-junta but rather correlated with a k-junta. How well can we estimate this correlation? This question was asked by De, Mossel, and Neeman [FOCS 2019], who gave an algorithm for the task making ~exp(k) queries. We present an improved algorithm that makes ~exp(sqrt{k}) many queries.
Along the way, we also give an algorithm, making poly(k) queries, that provides "implicit oracle access" to the underlying k-junta. Our techniques are Fourier analytical and introduce the notion of "normalized influences" that might be of independent interest.
https://eccc.weizmann.ac.il/report/2021/004/
To watch the talk:
- Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
- Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)