On the distribution of the fourier spectrum of Boolean functions
On the distribution of the fourier spectrum of Boolean functions
复制标题
关于布尔函数的傅立叶谱的分布
DOI：
10.1007/bf02785861
复制
发表时间：
2002
影响因子：
1
通讯作者：
J. Bourgain
中科院分区：
文献类型：
--
作者：
J. Bourgain
本文得到了{1，-1}N上布尔函数f的Fourier谱的尾分布的一般下界。粗略地说，固定k ∈ k+，并假设f本质上不是由有界数量（取决于k）的变量决定的，我们有：
$$\sum {\left| s \right|> k\left| {\hat f（S）}对|^2} \gtrsim k^{ - 1/2 - \varepsign} $$
.多数函数的例子表明，该结果基本上是最优的。
AbstractIn this paper we obtain a general lower bound for the tail distribution of the Fourier spectrum of Boolean functionsf on {1, −1}N. Roughly speaking, fixingk∈ℤ+ and assuming thatf is not essentially determined by a bounded number (depending onk) of variables, we have that
$$\sum {\left| s \right| > k\left| {\hat f(S)} \right|^2 } \gtrsim k^{ - 1/2 - \varepsilon } $$
. The example of the majority function shows that this result is basically optimal.