TCS+ Talk

The problem of testing whether an n-variable function is a k-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 f:{0,1}^n→{0,1} is a k-junta or ϵ-far from every k-junta must make Ω˜(k^(3/2)/ϵ) many queries. This result is essentially optimal given Blais's non-adaptive junta tester, which makes O˜(k^(3/2))/ϵ 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.