arXiv Open Access 2015

An inequality for the Fourier spectrum of parity decision trees

Eric Blais Li-Yang Tan Andrew Wan

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DM

Penulis (3)

Eric Blais

Li-Yang Tan

Andrew Wan

Format Sitasi

APA MLA BibTeX

Blais, E., Tan, L., Wan, A. (2015). An inequality for the Fourier spectrum of parity decision trees. https://arxiv.org/abs/1506.01055

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓