[1]   Miklós Ajtai: A non-linear time lower bound for Boolean branching programs. Theory of Computing, 1(8):149–176, 2005. Preliminary version in FOCS’99. [doi:10.4086/toc.2005.v001a008]

[2]   Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, and György Turán: Two lower bounds for branching programs. In Proc. 18th STOC, pp. 30–38. ACM Press, 1986. [doi:10.1145/12130.12134]

[3]   Noga Alon and Ravi B. Boppana: The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1–22, 1987. [doi:10.1007/BF02579196]

[4]   Kazuyuki Amano and Akira Maruoka: The potential of the approximation method. SIAM J. Comput., 33(2):433–447, 2004. Preliminary version in FOCS’96. [doi:10.1137/S009753970138445X]

[5]   Alexander E. Andreev: On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Mathematics Doklady, 31(3):530–534, 1985.

[6]   David A. Mix Barrington and Pierre McKenzie: Oracle branching programs and Logspace versus P. Inform. and Comput., 95(1):96–115, 1991. Preliminary version in MFCS’89. [doi:10.1016/0890-5401(91)90017-V]

[7]   David A. Mix Barrington and Howard Straubing: Superlinear lower bounds for bounded-width branching programs. J. Comput. System Sci., 50(3):374–381, 1995. Preliminary version in SCT’91. [doi:10.1006/jcss.1995.1029]

[8]   Paul Beame, Thathachar S. Jayram, and Michael E. Saks: Time-space tradeoffs for branching programs. J. Comput. System Sci., 63(4):542–572, 2001. Preliminary version in FOCS’98. [doi:10.1006/jcss.2001.1778]

[9]   Paul Beame, Michael E. Saks, Xiaodong Sun, and Erik Vee: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154–195, 2003. Preliminary version in FOCS’00. [doi:10.1145/636865.636867]

[10]   Charles H. Bennett: Time/space trade-offs for reversible computation. SIAM J. Comput., 18(4):766–776, 1989. [doi:10.1137/0218053]

[11]   Christer Berg and Staffan Ulfberg: Symmetric approximation arguments for monotone lower bounds without sunflowers. Comput. Complexity, 8(1):1–20, 1999. [doi:10.1007/s000370050017]

[12]    María Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen: On the relative complexity of resolution refinements and cutting planes proof systems. SIAM J. Comput., 30(5):1462–1484, 2000. Preliminary versions in FOCS’98 and ECCC. [doi:10.1137/S0097539799352474]

[13]   María Luisa Bonet, Toniann Pitassi, and Ran Raz: Lower bounds for cutting planes proofs with small coefficients. J. Symbolic Logic, 62(3):708–728, 1997. Preliminary version in STOC’95. JSTOR.

[14]   Ravi B. Boppana: Threshold functions and bounded depth monotone circuits. J. Comput. System Sci., 32(2):222–229, 1986. Preliminary version in STOC’84. [doi:10.1016/0022-0000(86)90027-9]

[15]   Ravi B. Boppana and Michael Sipser: The complexity of finite functions. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 757–804. Elsevier and MIT Press, 1990. [ACM:114886]

[16]   Allan Borodin: On relating time and space to size and depth. SIAM J. Comput., 6(4):733–744, 1977. [doi:10.1137/0206054]

[17]   Stephen A. Cook: An observation on time-storage trade off. J. Comput. System Sci., 9(3):308–316, 1974. Preliminary version in STOC’73. [doi:10.1016/S0022-0000(74)80046-2]

[18]   Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam: Pebbles and branching programs for tree evaluation. ACM Trans. Computation Theory, 3(2):4:1–4:43, 2012. Preliminary versions in FSTTCS’09 and MFCS’09. [doi:10.1145/2077336.2077337]

[19]   Jeff Edmonds, Russell Impagliazzo, Steven Rudich, and Jiří Sgall: Communication complexity towards lower bounds on circuit depth. Comput. Complexity, 10(3):210–246, 2001. Preliminary version in FOCS’91. [doi:10.1007/s00037-001-8195-x]

[20]   Bradley Efron and Charles Stein: The jackknife estimate of variance. Ann. Stat., 9(3):586–596, 1981. [doi:10.1214/aos/1176345462]

[21]   Anna Gál, Michal Koucký, and Pierre McKenzie: Incremental branching programs. Theory Comput. Syst., 43(2):159–184, 2008. Preliminary versions at Complexity of Boolean Functions and CSR’06. [doi:10.1007/s00224-007-9049-y]

[22]   Mikael Goldmann and Johan Håstad: A simple lower bound for monotone clique using a communication game. Inform. Process. Lett., 41(4):221–226, 1992. [doi:10.1016/0020-0190(92)90184-W]

[23]   Mikael Goldmann and Johan Håstad: Monotone circuits for connectivity have depth (log n)^2-o(1). SIAM J. Comput., 27(5):1283–1294, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795285631]

[24]   Michelangelo Grigni: Structure in Monotone Complexity. Ph. D. thesis, Massachusetts Institute of Technology, 1991. Available at CiteSeerX. [ACM:918937]

[25]   Michelangelo Grigni and Michael Sipser: Monotone separation of logarithmic space from logarithmic depth. J. Comput. System Sci., 50(3):433–437, 1995. Preliminary version in SCT’91. [doi:10.1006/jcss.1995.1033]

[26]   Armin Haken: Counting bottlenecks to show monotone P≠NP. In Proc. 36th FOCS, pp. 36–40. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492460]

[27]   Danny Harnik and Ran Raz: Higher lower bounds on monotone size. In Proc. 32nd STOC, pp. 378–387. ACM Press, 2000. Full version available at author’s home page. [doi:10.1145/335305.335349]

[28]   Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart: Upper and lower bounds for tree-like cutting planes proofs. In Proc. 9th Ann. Symp. on Logic in Computer Science (LICS’94), pp. 220–228. IEEE Comp. Soc. Press, 1994. [doi:10.1109/LICS.1994.316069]

[29]   Jan Johannsen: Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO - Theoretical Informatics and Applications, 35(3):277–286, 2001. [doi:10.1051/ita:2001120]

[30]   Neil D. Jones and William T. Laaser: Complete problems for deterministic polynomial time. Theor. Comput. Sci., 3(1):105–117, 1976. Preliminary version in STOC’74. [doi:10.1016/0304-3975(76)90068-2]

[31]   Stasys Jukna: Finite limits and monotone computations: The lower bounds criterion. In Proc. 12th IEEE Conf. on Computational Complexity (CCC’97), pp. 302–313, 1997. [doi:10.1109/CCC.1997.612325]

[32]   Mauricio Karchmer: On proving lower bounds for circuit size. In Proc. 8th IEEE Conf. on Structure in Complexity Theory (SCT’93), pp. 112–118. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336535]

[33]   Mauricio Karchmer, Ran Raz, and Avi Wigderson: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complexity, 5(3-4):191–204, 1995. Preliminary version in SCT’91. [doi:10.1007/BF01206317]

[34]   Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Preliminary version in STOC’88. [doi:10.1137/0403021]

[35]   Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. 8th IEEE Conf. on Structure in Complexity Theory (SCT’93), pp. 102–111, 1993. [doi:10.1109/SCT.1993.336536]

[36]   Maria M. Klawe: A tight bound for black and white pebbles on the pyramid. J. ACM, 32(1):218–228, 1985. Preliminary version in FOCS’83. [doi:10.1145/2455.214115]

[37]   Jan Krajíček: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symbolic Logic, 62(2):457–486, 1997. JSTOR.

[38]   Richard Královic: Time and space complexity of reversible pebbling. RAIRO - Theoretical Informatics and Applications, 38(2):137–161, 2004. Preliminary version in SOFSEM’01. [doi:10.1051/ita:2004008]

[39]   Matthias Krause: Lower bounds for depth-restricted branching programs. Inform. and Comput., 91(1):1–14, 1991. [doi:10.1016/0890-5401(91)90072-A]

[40]   Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp: Reversible space equals deterministic space. J. Comput. System Sci., 60(2):354–367, 2000. Preliminary version in CCC’97. [doi:10.1006/jcss.1999.1672]

[41]   Ketan Mulmuley: Lower bounds in a parallel model without bit operations. SIAM J. Comput., 28(4):1460–1509, 1999. [doi:10.1137/S0097539794282930]

[42]   Katsutoshi Nakayama and Akira Maruoka: Loop circuits and their relation to Razborov’s approximation model. Inform. and Comput., 119(2):154–159, 1995. [doi:10.1006/inco.1995.1083]

[43]   Èduard Ivanovič Nečiporuk: On a Boolean function. Soviet Mathematics Doklady, 7(4):999–1000, 1966.

[44]   Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1]

[45]   Aaron Potechin: Bounds on monotone switching networks for directed connectivity. In Proc. 51st FOCS, pp. 553–562. IEEE Comp. Soc. Press, 2010. An updated version to appear in Journal of the ACM. [doi:10.1109/FOCS.2010.58]

[46]   Ran Raz and Pierre McKenzie: Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999. Preliminary version in FOCS’97. [doi:10.1007/s004930050062]

[47]   Ran Raz and Avi Wigderson: Monotone circuits for matching require linear depth. J. ACM, 39(3):736–744, 1992. Preliminary version in STOC’90. [doi:10.1145/146637.146684]

[48]   Alexander A. Razborov: Lower bounds for the monotone complexity of some Boolean functions. Soviet Mathematics Doklady, 31(2):354–357, 1985.

[49]   Alexander A. Razborov: Lower bounds on monotone complexity of the logical permanent. Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485–493, 1985. [doi:10.1007/BF01157687]

[50]   Alexander A. Razborov: On the method of approximations. In Proc. 21st STOC, pp. 167–176. ACM Press, 1989. [doi:10.1145/73007.73023]

[51]   Alexander A. Razborov: Lower bounds of the complexity of symmetric Boolean functions of contact-rectifier circuits. Mathematical Notes of the Academy of Sciences of the USSR, 48(6):1226–1234, 1990. [doi:10.1007/BF01240265]

[52]   Alexander A. Razborov: Lower bounds for deterministic and nondeterministic branching programs. In 8th Internat. Symp. on Fundamentals of Computation Theory, 8th International Symposium (FCT’91), pp. 47–60, 1991. [doi:10.1007/3-540-54458-5_49]

[53]   Alexander A. Razborov, Avi Wigderson, and Andrew Chi-Chih Yao: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Combinatorica, 22(4):555–574, 2002. Preliminary version in STOC’97. [doi:10.1007/s00493-002-0007-7]

[54]   Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, 2008. Preliminary version in STOC’05. [doi:10.1145/1391289.1391291]

[55]   Benjamin Rossman: The monotone complexity of k-clique on random graphs. In Proc. 51st FOCS, pp. 193–201. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.26]

[56]   Janos Simon and Shi-Chun Tsai: On the bottleneck counting argument. Theoret. Comput. Sci., 237(1-2):429–437, 2000. Preliminary version in CCC’97. [doi:10.1016/S0304-3975(99)00321-7]

[57]   Éva Tardos: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, 1988. [doi:10.1007/BF02122563]

[58]   Luca Trevisan: Extractors and pseudorandom generators. J. ACM, 48(4):860–879, 2001. Preliminary version in STOC’99. [doi:10.1145/502090.502099]

[59]   Dustin Wehr: Pebbling and branching programs solving the tree evaluation problem. Technical report, 2010. [arXiv:1002.4676]

[60]   Dustin Wehr: Lower bound for deterministic semantic-incremental branching programs solving GEN. Technical report, 2011. [arXiv:1101.2705]

[61]   Andrew Chi-Chih Yao: Circuits and local computation. In Proc. 21st STOC, pp. 186–196. ACM Press, 1989. [doi:10.1145/73007.73025]

[62]   Andrew Chi-Chih Yao: A lower bound for the monotone depth of connectivity. In Proc. 35th FOCS, pp. 302–308. IEEE Comp. Soc. Press, 1994. [doi:10.1109/SFCS.1994.365685]