An inequality for the Fourier spectrum of parity decision trees

Eric Blais, Li-Yang Tan, Andrew Wan

We give a new bound on the sum of the linear Fourier coefficients of a Boolean function in terms of its parity decision tree complexity. This result generalizes an inequality of O'…