Testing Booleanity and the Uncertainty Principle

Details Testing Booleanity and the Uncertainty Principle Testing Booleanity and the Uncertainty Principle

2012-04-04

arxiv.org/abs/1204.0944v1

Computer Science

Discrete Mathematics

11 pages

Scientific paper

Let f:{-1,1}^n -> 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 naive 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.

Affiliated with

Also associated with

No associations

Rating

Testing Booleanity and the Uncertainty Principle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Booleanity and the Uncertainty Principle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Booleanity and the Uncertainty Principle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32198