Paper Info
Title
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
Abstract
We prove a lower bound of Ω(n1/2-c), for all c> 0, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an n-variable Boolean function is monotone versus constant-far from monotone. This improves a ~Ω(n1/5) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n1/2/ε2) by Khot et al. [13].
Year
DOI
Venue
2015
10.1145/2746539.2746570
ACM Symposium on Theory of Computing
DocType
Volume
ISSN
Conference
abs/1412.5657
0737-8017
Citations 
PageRank 
References 
12
0.74
9
Authors
4
Name
Order
Citations
PageRank
Xi Chen195066.32
Anindya De223924.77
Rocco A. Servedio31656133.28
Li-Yang Tan415924.26