Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428189 | Information Processing Letters | 2007 | 5 Pages |
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 rather “flat” Fourier spectrum and thus implies several lower bounds on some of its complexity measures.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics