Bounds on the Fourier coefficients of the weighted sum function
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. (c) 2007 Elsevier B.V. All rights reserved.
fourier coefficients weighted sums boolean function computational complexity