论文标题
有关切换引理的注释
Notes on switching lemmas
论文作者
论文摘要
我们证明了三个切换引理，对于独立设置变量的随机限制；对于在块中设置变量的随机限制（均由HASTAD [HASTAD 86]引起）；并用于适合徒的鸽子原理的分布[Beame等。 94，Krajicek等。 95]。这些证明是基于Beame的版本[Beame 94] Razborov在[Razborov 93]中的开关引理的证明，除非使用加权限制的家族而不是限制的家族，而这些家族的大小都是相同的。这遵循[Beame 94]中的Beame的建议。结果在于哈斯达德和拉兹博罗夫的证明方法之间。我们以与HASTAD相似的方式使用概率论点，而不是计数论证，而不是像HASTAD一样，使用涉及条件概率的归纳假设对我们的公式中的术语进行归纳，我们明确地构建一个函数以限制整个公式的概率。
We prove three switching lemmas, for random restrictions for which variables are set independently; for random restrictions where variables are set in blocks (both due to Hastad [Hastad 86]); and for a distribution appropriate for the bijective pigeonhole principle [Beame et al. 94, Krajicek et al. 95]. The proofs are based on Beame's version [Beame 94] of Razborov's proof of the switching lemma in [Razborov 93], except using families of weighted restrictions rather than families of restrictions which are all the same size. This follows a suggestion of Beame in [Beame 94]. The result is something between Hastad's and Razborov's methods of proof. We use probabilistic arguments rather than counting ones, in a similar way to Hastad, but rather than doing induction on the terms in our formula with an inductive hypothesis involving conditional probability, as Hastad does, we explicitly build one function to bound the probabilities for the whole formula.
