ECCC-Report TR12-031https://eccc.weizmann.ac.il/report/2012/031Comments and Revisions published for TR12-031en-usTue, 12 Nov 2013 06:29:42 +0200
Revision 1
| Testing Booleanity and the Uncertainty Principle |
Tom Gur,
Omer Tamuz
https://eccc.weizmann.ac.il/report/2012/031#revision1Let $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.Tue, 12 Nov 2013 06:29:42 +0200https://eccc.weizmann.ac.il/report/2012/031#revision1
Paper TR12-031
| Testing Booleanity and the Uncertainty Principle |
Tom Gur,
Omer Tamuz
https://eccc.weizmann.ac.il/report/2012/031Let $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.Wed, 04 Apr 2012 16:39:39 +0300https://eccc.weizmann.ac.il/report/2012/031