The non-adaptive query complexity of testing k-parities

Harry Buhrman, David Garcia-Soriano, Arie Matsliah +1

We prove tight bounds of Theta(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…