Chicago Journal of Theoretical Computer Science

Volume 2013

Article 14

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

Testing Booleanity and the Uncertainty Principle

Tom Gur
Faculty of Mathematics and Computer Science
Weizmann Institute of Science
tom.gur AT weizmann DOT ac DOT il


Omer Tamuz
Microsoft Research New England
Cambridge, MA
omertamuz AT gmail DOT com

November 10, 2013


Let $f:\{-1,1\}^n \to$ R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in $\{-1,1\}$.

We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most $k$ terms must either be Boolean, or output values different than $-1$ or $1$ for a fraction of at least $2/(k+2)^2$ of its domain.

It follows that given oracle access to $f$, together with the guarantee that its representation as a multilinear polynomial has at most $k$ terms, one can test Booleanity using $O(k^2)$ queries. We show an $\Omega(k)$ queries lower bound for this problem.

Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.

Submitted December 26, 2012, revised November 6, 2013; published November 10, 2013.

DOI: 10.4086/cjtcs.2013.014

[] Article 13 [] Volume 14, Article 1
[back] Volume 2013 [back] Published articles
[CJCTS home]