__
Revision #1 to TR12-031 | 12th November 2013 06:29
__
#### Testing Booleanity and the Uncertainty Principle

**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.

**Changes to previous version:**
Journal version (Chicago Journal of Theoretical Computer Science 2013, Article 14).

__
TR12-031 | 4th April 2012 16:30
__

#### Testing Booleanity and the Uncertainty Principle

**Abstract:**
Let $f:\{-1,1\}^n \to \mathbb{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 black box 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.

We also consider the problem of deciding if a function is Boolean,

given its explicit representation as a $k$ term multilinear

polynomial. The na\"ive approach of evaluating it at every input

has $O(kn2^n)$ time complexity. For large $k$ (i.e, exponential) we

present a simple randomized $O(kn\sqrt{2^n})$ algorithm. For small

$k$ we show how the problem can be solved deterministically in

$O(k^3n)$.

Our proofs crucially use Hirschman's entropic version of

Heisenberg's uncertainty principle.