Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-031 | 12th November 2013 06:29

Testing Booleanity and the Uncertainty Principle

RSS-Feed




Revision #1
Authors: Tom Gur, Omer Tamuz
Accepted on: 12th November 2013 06:29
Downloads: 408
Keywords: 


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


Paper:

TR12-031 | 4th April 2012 16:30

Testing Booleanity and the Uncertainty Principle





TR12-031
Authors: Tom Gur, Omer Tamuz
Publication: 4th April 2012 16:39
Downloads: 1147
Keywords: 


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.



ISSN 1433-8092 | Imprint