Testing Booleanity and the Uncertainty Principle

Tom Gur, Omer Tamuz

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 Boole…