DagSemProc.06111.5.pdf
- Filesize: 297 kB
- 9 pages
Document
Bounds on the Fourier Coefficients of the Weighted Sum Function
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-20
Cite As Get BibTex
Igor E. Shparlinski. Bounds on the Fourier Coefficients of the Weighted Sum Function. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06111.5
Abstract
We estimate Fourier coefficients of a Boolean function which has recently been introduced in the study of read-once branching programs. Our bound implies that this function has an asymptotically ``flat'' Fourier spectrum and thus implies several lower bounds of its various complexity measures.
Subject Classification
Keywords
- Fourier coefficients
- congruences
- average sensitivity
- decision tree
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads