论文标题
最佳的“直到结束”定理
An Optimal "It Ain't Over Till It's Over" Theorem
论文作者
论文摘要
我们研究具有最大影响力的布尔函数的概率在随机限制下变得恒定。让$ f $是布尔函数，使$ f $的差异为$ω（1）$，其所有个人影响都由$τ$界定。我们表明，当限制除$ρ= \tildeΩ（（（\ log（1/τ））^{ - 1}）$坐标分数时，限制函数仍然没有压倒性的概率。该界限本质上是最佳的，如部落功能$ \ mathrm {tribes} = \ mathrm {and} _ {n/c \ log n} \ circ \ mathrm {or} _ {c \ log n} $。 我们将其扩展到抗浓缩结果，表明限制函数具有非平凡的差异，概率$ 1-O（1）$。这给出了“直到结束”定理的鲜明版本，这是由于mossel，O'Donnell和Oleszkiewicz。我们的证明是离散的，并且避免了不变性原则的使用。 我们还显示了上述结果的两个后果：（i）作为推论，我们证明，对于均匀的随机输入$ x $，$ f $ $ x $的块灵敏度为$ x $ as $ \tildeΩ（\ log（1/τ））$，概率为$ 1-O（1-O（1）$。应将其与Kahn，Kalai和Linial的结果的含义进行比较，这意味着$ F $的平均块灵敏度为$ω（\ log（1/τ））$。 （ii）将我们的证明与由于O'Donnell，Saks，Schramm和Ferveio的众所周知的结果结合在一起，也可以得出结论，可以得出结论：限制除$ρ= \tildeΩ（1/\ sqrt {\ log log（log log（1/° $ω（τ^{ - θ（ρ）}）$带有概率$ω（1）$。
We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let $f$ be a Boolean function such that the variance of $f$ is $Ω(1)$ and all its individual influences are bounded by $τ$. We show that when restricting all but a $ρ=\tildeΩ((\log(1/τ))^{-1})$ fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $\mathrm{TRIBES}=\mathrm{AND}_{n/C\log n}\circ\mathrm{OR}_{C\log n}$. We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability $1-o(1)$. This gives a sharp version of the "it ain't over till it's over" theorem due to Mossel, O'Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle. We also show two consequences of our above result: (i) As a corollary, we prove that for a uniformly random input $x$, the block sensitivity of $f$ at $x$ is $\tildeΩ(\log(1/τ))$ with probability $1-o(1)$. This should be compared with the implication of Kahn, Kalai, and Linial's result, which implies that the average block sensitivity of $f$ is $Ω(\log(1/τ))$. (ii) Combining our proof with a well-known result due to O'Donnell, Saks, Schramm, and Servedio, one can also conclude that: Restricting all but a $ρ=\tildeΩ(1/\sqrt{\log (1/τ) })$ fraction of the coordinates of a monotone function $f$, then the restricted function has decision tree complexity $Ω(τ^{-Θ(ρ)})$ with probability $Ω(1)$.
