arXiv:1209.3849 · Chicago Journal of Theoretical Computer Science
The non-adaptive query complexity of testing k-parities
Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf
Abstract
We prove tight bounds of Θ(k log k) 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 [4] to get lower bounds for testing from communication complexity with an Ω(k log k) lower bound for the one-way communication complexity of k-disjointness.