Chicago Journal of Theoretical Computer Science

Volume 2013

Article 6

Published by the Department of Computer Science, The University of Chicago.


The non-adaptive query complexity of testing k-parities

Harry Buhrman
CWI and University of Amsterdam, The Netherlands
burman AT cwi DOT nl

David García-Soriano
Yahoo! Research, Barcelona, Spain
elhipercubo AT gmail DOT com

Arie Matsliah
Google Research, Mountain View, USA
arie.matsliah AT gmail DOT com

and

Ronald de Wolf
CWI and University of Amsterdam, The Netherlands
rdewolf AT cwi DOT nl

July 2, 2013

Abstract

We prove tight bounds of $\Theta(k \log k)$ queries for non-adaptively testing whether a function $f: \{ 0,1 \}^n \to \{ 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 $\Omega(k\log k)$ lower bound for the one-way communication complexity of $k$-disjointness.


Submitted July 13, 2012, revised December 23, 2012, and June 30, 2013; published July 2, 2013.

DOI: 10.4086/cjtcs.2013.006


[] Article 5 [] Article 7
[back] Volume 2013 [back] Published articles
[CJCTS home]