We prove tight bounds of Q(k log k) queries for non-adaptively testing whether a function f :f0; 1g n !f0; 1g is a k-parity or far from any k-parity. The lower bound combines a recent method of Blais, Brody and Matulef (4) to get lower bounds for testing from communication complexity with an W(k log k) lower bound for the one-way communication complexity of k-disjointness.
['Harry Buhrman', 'David García-Soriano', 'Arie Matsliah', 'Ronald de Wolf']
The non-adaptive query complexity of testing k-parities