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.
Journal version (Chicago Journal of Theoretical Computer Science 2013, Article 14).
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.
