@article{10.2307/2275250,
    Abstract = {LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and $\bigwedge, \bigvee$ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set Td n of depth d sequents of total size O(n3 + d) which are refutable in LK by depth d + 1 proof of size exp(O(log2 n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets Td n express a weaker form of the pigeonhole principle.},
    Author = {Kraji{\v c}ek, Jan},
    File = {Lower Bounds to the Size of Constant-Depth Propositional Proofs - 2275250 - a - a - a.pdf},
    ISSN = {00224812},
    Journal = {The Journal of Symbolic Logic},
    Number = {1},
    Pages = {73--86},
    Publisher = {Association for Symbolic Logic},
    Title = {Lower Bounds to the Size of Constant-Depth Propositional Proofs},
    URL = {http://www.jstor.org/stable/2275250},
    Volume = {59},
    Year = {1994},
    bdsk-url-1 = {http://www.jstor.org/stable/2275250},
    date-added = {2019-10-14 17:54:09 +0200},
    date-modified = {2019-10-14 17:54:09 +0200},
    doi = {10.2307/2275250}
}

@article{10.2307/2275250, Abstract = {LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and $\bigwedge, \bigvee$ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set Td n of depth d sequents of total size O(n3 + d) which are refutable in LK by depth d + 1 proof of size exp(O(log2 n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets Td n express a weaker form of the pigeonhole principle.}, Author = {Kraji{\v c}ek, Jan}, File = {Lower Bounds to the Size of Constant-Depth Propositional Proofs - 2275250 - a - a - a.pdf}, ISSN = {00224812}, Journal = {The Journal of Symbolic Logic}, Number = {1}, Pages = {73--86}, Publisher = {Association for Symbolic Logic}, Title = {Lower Bounds to the Size of Constant-Depth Propositional Proofs}, URL = {http://www.jstor.org/stable/2275250}, Volume = {59}, Year = {1994}, bdsk-url-1 = {http://www.jstor.org/stable/2275250}, date-added = {2019-10-14 17:54:09 +0200}, date-modified = {2019-10-14 17:54:09 +0200}, doi = {10.2307/2275250} }