The non-adaptive query complexity of testing k-parities
Venue
Chicago Journal of Theoretical Computer Science,
vol. 2013 (2013), pp. 1-11
Publication Year
2013
Authors
Harry Buhrman, David Garcia, Arie Matsliah, Ronald de Wolf
BibTeX
Abstract
We prove tight bounds of Θ(klogk) queries for non-adaptively testing whether a
function f:{0,1}^n→{0,1} is a k-parity or far from any k-parity. The lower bound
combines a recent method of Blais, Brody and Matulef to get lower bounds for
testing from communication complexity with an Ω(klogk) lower bound for the one-way
communication complexity of k-disjointness.