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

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.

• The article: PDF (210 KB)
• Source material: ZIP (107 KB)
• BibTeX entry for this article (303 bytes)

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

© 2013 Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf
Licensed under a Creative Commons Attribution License

Article 5

Article 7

Volume 2013

Published articles