#

### 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

Rehovot

Israel

`tom.gur AT weizmann DOT ac DOT il`

and

Omer Tamuz

Microsoft Research New England

Cambridge, MA

USA

`omertamuz AT gmail DOT com`

*November 10, 2013*
#### Abstract

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.

- The article:
**PDF** (231 KB)
- Source material:
**ZIP** (81 KB)
**BibTeX** entry for this article (250 bytes)

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

Article 13
Volume 14, Article 1

Volume 2013
Published articles