Paper Info
Title
Improved Bounds for Testing Juntas
Abstract
We consider the problem of testing functions for the property of being a k-junta (i.e., of depending on at most kvariables). Fischer, Kindler, Ron, Safra, and Samorodnitsky (J. Comput. Sys. Sci., 2004) showed that $\tilde{O}(k^2)/\epsilon$ queries are sufficient to test k-juntas, and conjectured that this bound is optimal for non-adaptive testing algorithms.Our main result is a non-adaptive algorithm for testing k-juntas with $\tilde{O}(k^{3/2})/\epsilon$ queries. This algorithm disproves the conjecture of Fischer et al.We also show that the query complexity of non-adaptive algorithms for testing juntas has a lower bound of $\min \big(\tilde{\Omega}(k/\epsilon), 2^k/k\big)$, essentially improving on the previous best lower bound of 茂戮驴(k).
Year
DOI
Venue
2008
10.1007/978-3-540-85363-3_26
APPROX-RANDOM
Keywords
Field
DocType
main result,improved bounds,query complexity,testing juntas,non-adaptive algorithm,j. comput,non-adaptive testing algorithm,lower bound,adaptive testing
Boolean function,Discrete mathematics,Combinatorics,Upper and lower bounds,Omega,Tilde,Statistical distance,Conjecture,Input function,Mathematics
Conference
Volume
ISSN
Citations 
5171
0302-9743
18
PageRank 
References 
Authors
0.86
15
1
Name
Order
Citations
PageRank
Eric Blais128622.49