Article ID Journal Published Year Pages File Type
428189 Information Processing Letters 2007 5 Pages PDF
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