The next TCS+ talk will take place next Wednesday, June 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Erik Waingarten (Columbia University) will will speak about “Settling the query complexity of non-adaptive junta testing” (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
The problem of testing whether an -variable function is a -junta has been one of the main problems in property testing. In this talk, I will show that any non-adaptive algorithm that tests whether an unknown Boolean function is a -junta or -far from every -junta must make many queries. This result is essentially optimal given Blais’s non-adaptive junta tester, which makes queries and shows that adaptivity enables polynomial savings in query complexity for junta testing. At a very high level, the proof proceeds by reducing the non-adaptive junta testing of a new class of random Boolean functions to a problem of distinguishing two binomial distributions with a specific kind of noisy query.This is joint work with Xi Chen, Rocco Servedio, Li-Yang Tan, and Jinyu Xie.