Google Research

The non-adaptive query complexity of testing k-parities

  • Harry Buhrman
  • David Garcia
  • Arie Matsliah
  • Ronald de Wolf
Chicago Journal of Theoretical Computer Science, vol. 2013 (2013), pp. 1-11

Abstract

We prove tight bounds of Θ(klogk) 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 to get lower bounds for testing from communication complexity with an Ω(klogk) lower bound for the one-way communication complexity of k-disjointness.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work