In:
Journal of the ACM, Association for Computing Machinery (ACM), Vol. 65, No. 6 ( 2018-12-31), p. 1-18
Abstract:
We prove 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 for a wide range of parameters k and ϵ. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω ˜ ( k 3/2 ) / ϵ queries. Combined with the known existence of an adaptive tester which makes O ( k log k + k /ϵ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.
Type of Medium:
Online Resource
ISSN:
0004-5411
,
1557-735X
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2018
detail.hit.zdb_id:
2006500-0
detail.hit.zdb_id:
6759-3
Permalink