An inequality for the Fourier spectrum of parity decision trees

2015/05/20 by Blais, Eric, Tan, Li-Yang, Wan, Andrew
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1506.01055

Abstract

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'Donnell and Servedio for regular decision trees. We use this bound to obtain the first non-trivial lower bound on the parity decision tree complexity of the recursive majority function.

Related

• Parity Decision Tree Complexity is Greater Than Granularity
• On parity decision trees for Fourier-sparse Boolean functions
• Fourier Growth of Parity Decision Trees
• On the Structure of Boolean Functions with Small Spectral Norm
• Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity