Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 10, 2013 | Supplemental Material + Submitted + Published
Journal Article Open

Testing Booleanity and the Uncertainty Principle

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

1204.0944v1.pdf
Files (647.1 kB)
Name Size Download all
md5:b395cbc163e95b4bf76a121baa2f3a4a
165.4 kB Preview Download
md5:ffee3aff67886fa9dfc77f635b4812d5
170.5 kB Preview Download
md5:a504c3e94c1093ebb0d0d5c4bd190759
80.6 kB Preview Download
md5:9bd26097a03e82106a89cdcb844f3d50
230.6 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023