Testing Booleanity and the Uncertainty Principle
- Creators
- Gur, Tom
- Tamuz, Omer
Abstract
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)² 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²) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.
Additional Information
© 2013 Tom Gur and Omer Tamuz. Licensed under a Creative Commons Attribution License (CC-BY). Submitted December 26, 2012, revised November 6, 2013; published November 10, 2013. Research supported by an Israel Science Foundation grant and by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation. Supported by ISF grant 1300/08. Omer Tamuz is a recipient of the Google Europe Fellowship in Social Computing, and this research is supported in part by this Google Fellowship. The authors would like to thank Elchanan Mossel for a helpful initial discussion of the problem and for suggesting the application to property testing. We would like to thank Adi Shamir for suggesting the relevance to cryptography, and we would like to thank Oded Goldreich for discussions regarding the relevance to property testing. Last, we would like to thank the anonymous referees for the helpful comments that allowed us to improve the presentation of the results.Attached Files
Published - cj13-14.pdf
Submitted - 1204.0944.pdf
Submitted - 1204.0944v1.pdf
Supplemental Material - cj13-14.zip
Files
Additional details
- Eprint ID
- 71919
- Resolver ID
- CaltechAUTHORS:20161110-144803099
- I-CORE Program of the Planning and Budgeting Committee
- 1300/08
- Israel Science Foundation
- Created
-
2016-11-11Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field