@article{Pitassi:1993aa,
    Abstract = {In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an Ω(loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general H{\aa}stad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.},
    Author = {Pitassi, Toniann and Beame, Paul and Impagliazzo, Russell},
    File = {Exponential Lower Bounds for the Pigeonhole Principle- - a - a - a - i.pdf},
    ISBN = {1420-8954},
    Journal = {computational complexity},
    Number = {2},
    Pages = {97--140},
    Title = {Exponential lower bounds for the pigeonhole principle},
    URL = {https://doi.org/10.1007/BF01200117},
    Volume = {3},
    Year = {1993},
    bdsk-url-1 = {https://doi.org/10.1007/BF01200117},
    da = {1993/06/01},
    date-added = {2020-02-12 08:44:39 +0100},
    date-modified = {2020-02-12 08:44:39 +0100},
    id = {Pitassi1993},
    ty = {JOUR},
    doi = {10.1007/BF01200117}
}

@article{Pitassi:1993aa, Abstract = {In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an Ω(loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general H{\aa}stad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.}, Author = {Pitassi, Toniann and Beame, Paul and Impagliazzo, Russell}, File = {Exponential Lower Bounds for the Pigeonhole Principle- - a - a - a - i.pdf}, ISBN = {1420-8954}, Journal = {computational complexity}, Number = {2}, Pages = {97--140}, Title = {Exponential lower bounds for the pigeonhole principle}, URL = {https://doi.org/10.1007/BF01200117}, Volume = {3}, Year = {1993}, bdsk-url-1 = {https://doi.org/10.1007/BF01200117}, da = {1993/06/01}, date-added = {2020-02-12 08:44:39 +0100}, date-modified = {2020-02-12 08:44:39 +0100}, id = {Pitassi1993}, ty = {JOUR}, doi = {10.1007/BF01200117} }