An inequality for the Fourier spectrum of parity decision trees
classification
💻 cs.DM
keywords
decisionboundparitycomplexityfourierfunctioninequalitytree
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{S3JP5ZBP}
Prints a linked pith:S3JP5ZBP badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.