2022/02/11 by Neil Thapen, Thapen, Neil
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Probability (math.PR) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2202.05651
openalex publication_date 2022/02/11 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
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.