Bounds on the Fourier coefficients of the weighted sum function

Igor E. Shparlinski

doi:10.1016/j.ipl.2007.02.011

Bounds on the Fourier coefficients of the weighted sum function

Igor E. Shparlinski^*

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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.

Original language	English
Pages (from-to)	83-87
Number of pages	5
Journal	Information Processing Letters
Volume	103
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2007.02.011
Publication status	Published - 31 Jul 2007

Access to Document

10.1016/j.ipl.2007.02.011

Cite this

@article{82fa01b6dd30484b80c819a4087698f4,

title = "Bounds on the Fourier coefficients of the weighted sum function",

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.",

author = "Shparlinski, {Igor E.}",

year = "2007",

month = jul,

day = "31",

doi = "10.1016/j.ipl.2007.02.011",

language = "English",

volume = "103",

pages = "83--87",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Bounds on the Fourier coefficients of the weighted sum function

AU - Shparlinski, Igor E.

PY - 2007/7/31

Y1 - 2007/7/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34248141839&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2007.02.011

DO - 10.1016/j.ipl.2007.02.011

M3 - Article

AN - SCOPUS:34248141839

SN - 0020-0190

VL - 103

SP - 83

EP - 87

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Bounds on the Fourier coefficients of the weighted sum function

Abstract

Access to Document

Other files and links

Fingerprint

Cite this