Understand
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.
Built on
Probabilistic boolean decision trees and the complexity of evaluating game trees
Michael E. Saks and Avi Wigderson · 1986
Earlier work this paper cites.
Elements of Information Theory
Thomas M. Cover and Joy A. Thomas · 1991
Earlier work this paper cites.
Machine learning: a tour through some favorite results, directions, and open problems
Avrim Blum · 2003
Earlier work this paper cites.
Two applications of information complexity
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2003
Earlier work this paper cites.
Learning monotone decision trees in polynomial time
Ryan O’Donnell and Rocco Servedio · 2008
Earlier work this paper cites.
On the communication complexity of xor functions
Ashley Montanaro and Tobias Osborne · 2009
Earlier work this paper cites.
Communication complexities of symmetric xor functions
Zhiqiang Zhang and Yaoyun Shi · 2009
Earlier work this paper cites.
Similar
On the parity complexity measures of boolean functions
Zhiqiang Zhang and Yaoyun Shi · 2010
Cited alongside, same era.
Improved bounds for the randomized decision tree complexity of recursive majority
Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao · 2011
Cited alongside, same era.
Dispersers for affine sources with sub-polynomial entropy
Ronen Shaltiel · 2011
Cited alongside, same era.
Affine dispersers from subspace polynomials
Eli Ben-Sasson and Swastik Kopparty · 2012
Cited alongside, same era.
Open problems in analysis of Boolean functions
Ryan O’Donnell · 2012
Cited alongside, same era.
An improved lower bound for the randomized decision tree complexity of recursive majority,
Nikos Leonardos · 2013
Cited alongside, same era.
Then
Improved bounds for the randomized decision tree complexity of recursive majority
Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, and David Xiao · 2013
Later among the works it cites.
Fourier sparsity, spectral norm, and the log-rank conjecture
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang · 2013
Later among the works it cites.
Two structural results for low degree polynomials and applications
Gil Cohen and Avishay Tal · 2014
Later among the works it cites.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Later among the works it cites.
A composition theorem for parity kill number
Ryan O’Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, and Yu Zhao · 2014
Later among the works it cites.
On the structure of boolean functions with small spectral norm
Amir Shpilka, Avishay Tal, and Ben Lee Volk · 2014
Later among the works it cites.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…