期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let f:−11nR 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 −11 .
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(k2) queries. We
show an (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(kn2n) time complexity. For large k (i.e, exponential) we
present a simple randomized O(kn2n) algorithm. For small
k we show how the problem can be solved deterministically in
O(k3n).
Our proofs crucially use Hirschman's entropic version of
Heisenberg's uncertainty principle.
