论文标题
布尔函数的紧密变型型范围
Tight Chang's-lemma-type bounds for Boolean functions
论文作者
论文摘要
Chang的引理（Duke Mathematical Journal，2002年）是一个经典的结果，其在数学和计算机科学领域的多个领域的应用。对于布尔函数$ f $，在{-1,1}中取值的$ r（f）$表示其傅立叶等级。对于每个正阈值$ t $，Chang's Lemma在$ wt（f）上提供了一个下限：= \ pr [f（x）= - 1] $，其字符的跨度具有至少$ 1/t $的傅立叶系数。我们检查了Chang的引理W.R.T.的紧密度阈值的以下三个自然设置： - $ f $的傅立叶稀疏性，表示为$ k（f）$， - $ f $的傅立叶最大 - 塞普 - entropy，表示为$ k'（f）$，定义为$ \ max \ {1/| \ hat {f}（s）| ：\ hat {f}（s）\ neq 0 \} $， - $ f $的傅立叶最大排名entropy，表示为$ k''（f）$，定义为最小$ t $，以使其傅立叶系数至少为$ 1/t $的绝对值中的字符跨越了尺寸$ r（f）$的空间。 在这些措施方面，我们证明了$ wt（f）$的新下限。我们的下限之一是Sanyal（TOC，2019年），在$ k（f）$方面，以$ k（f）$表示，以$ r（f）$上的$ r（f）$进行了完善。另一个下限是基于我们对Chattopadhyay，Hatami，Lovett和Tal（ITCS，2019年）的改善，其级别的绝对值为-1美元$ 1 $ fourier系数。我们还表明，对于阈值的这些选择，Chang的引理渐近地超过了我们所涉及的参数的大多数设置的界限。 接下来，我们证明，通过构建函数（是地址函数的修改），我们的界限对于所涉及的各种参数而言是紧密的。最后，我们构建了布尔功能$ f $ - 我们的下限渐近匹配$ wt（f）$，并且 - 对于任何选择阈值$ t $，从Chang的引理中获得的下限渐近小于$ wt（f）$。
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each positive threshold $t$, Chang's lemma provides a lower bound on $wt(f):=\Pr[f(x)=-1]$ in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least $1/t$. We examine the tightness of Chang's lemma w.r.t. the following three natural settings of the threshold: - the Fourier sparsity of $f$, denoted $k(f)$, - the Fourier max-supp-entropy of $f$, denoted $k'(f)$, defined to be $\max \{1/|\hat{f}(S)| : \hat{f}(S) \neq 0\}$, - the Fourier max-rank-entropy of $f$, denoted $k''(f)$, defined to be the minimum $t$ such that characters whose Fourier coefficients are at least $1/t$ in absolute value span a space of dimension $r(f)$. We prove new lower bounds on $wt(f)$ in terms of these measures. One of our lower bounds subsumes and refines the previously best known upper bound on $r(f)$ in terms of $k(f)$ by Sanyal (ToC, 2019). Another lower bound is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of the absolute values of the level-$1$ Fourier coefficients. We also show that Chang's lemma for the these choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions (which are modifications of the Addressing function) witnessing their tightness. Finally we construct Boolean functions $f$ for which - our lower bounds asymptotically match $wt(f)$, and - for any choice of the threshold $t$, the lower bound obtained from Chang's lemma is asymptotically smaller than $wt(f)$.
