Monotone Circuit Lower Bounds from Resolution

by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov

Theory of Computing, Volume 16(13), pp. 1-30, 2020

Bibliography with links to cited articles

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

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

[3]   Alexander E. Andreev: On a method for obtaining lower bounds for the complexity of individual monotone functions. Dokl. Math., 282(5):1033–1037, 1985. Link at Math-Net.ru.

[4]   Albert Atserias and Víctor Dalmau: A combinatorial characterization of resolution width. J. Comput. System Sci., 74(3):323–334, 2008. [doi:10.1016/j.jcss.2007.06.025]

[5]   Paul Beame, Trinh Huynh, and Toniann Pitassi: Hardness amplification in proof complexity. In Proc. 42nd STOC, pp. 87–96. ACM Press, 2010. [doi:10.1145/1806689.1806703]

[6]   Paul Beame and Toniann Pitassi: Propositional proof complexity: Past, present, and future. In Current Trends in Theoretical Computer Science: Entering the 21st Century, pp. 42–70. World Scientific, 2001. [doi:10.1142/9789812810403_0001, ECCC:TR98-067]

[7]   Paul Beame, Toniann Pitassi, and Nathan Segerlind: Lower bounds for Lovász–Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845–869, 2007. [doi:10.1137/060654645]

[8]   Eli Ben-Sasson and Avi Wigderson: Short proofs are narrow—resolution made simple. J. ACM, 48(2):149–169, 2001. [doi:10.1145/375827.375835]

[9]   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]

[10]   Maria Luisa Bonet, Toniann Pitassi, and Ran Raz: Lower bounds for cutting planes proofs with small coefficients. J. Symbolic Logic, 62(3):708–728, 1997. [doi:10.2307/2275569]

[11]   Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay: Simulation theorems via pseudo-random properties. Comput. Complexity, 28:617–659, 2019. [doi:10.1007/s00037-019-00190-7, arXiv:1704.06807]

[12]   William Cook, Collette Coullard, and György Turán: On the complexity of cutting-plane proofs. Discr. Appl. Math., 18(1):25–38, 1987. [doi:10.1016/0166-218X(87)90039-4]

[13]   Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals: How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proc. 57th FOCS, pp. 295–304. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.40]

[14]   Noah Fleming, Denis Pankratov, Toniann Pitassi, and Robert Robere: Random Θ(log n)-CNFs are hard for cutting planes. In Proc. 58th FOCS, pp. 109–120. IEEE Comp. Soc., 2017. Update: ECCC TR17-045. [doi:10.1109/FOCS.2017.19]

[15]   Anna Gál: A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complexity, 10(4):277–296, 2001. [doi:10.1007/s000370100001]

[16]   Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov: Monotone circuit lower bounds from resolution. In Proc. 50th STOC, pp. 902–911. ACM Press, 2018. [doi:10.1145/3188745.3188838]

[17]   Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson: Query-to-communication lifting for PNP. Comput. Complexity, 28(1):113–144, 2019. Preliminary version in CCC’17. [doi:10.1007/s00037-018-0175-5]

[18]   Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov: Adventures in monotone complexity and TFNP. In Proc. 10th Innovations in Theoret. Comp. Sci. (ITCS’19), pp. 38:1–38:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.38]

[19]   Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman: Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835–1869, 2016. [doi:10.1137/15M103145X]

[20]   Mika Göös and Toniann Pitassi: Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778–1806, 2018. Preliminary version in STOC’14. [doi:10.1137/16M1082007]

[21]   Mika Göös, Toniann Pitassi, and Thomas Watson: Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435–2450, 2018. Preliminary version in FOCS’15. [doi:10.1137/16M1059369]

[22]   Mika Göös, Toniann Pitassi, and Thomas Watson: Query-to-communication lifting for BPP. SIAM J. Comput., 49(4):132–143, 2020. Preliminary version in FOCS’17. [doi:10.1137/17M115339X]

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

[24]   Armin Haken and Stephen A. Cook: An exponential lower bound for the size of monotone real circuits. J. Comput. System Sci., 58(2):326–335, 1999. [doi:10.1006/jcss.1998.1617]

[25]   Danny Harnik and Ran Raz: Higher lower bounds on monotone size. In Proc. 32nd STOC, pp. 378–387. ACM Press, 2000. [doi:10.1145/335305.335349]

[26]   Pavel Hrubeš and Pavel Pudlák: Random formulas, monotone circuits, and interpolation. In Proc. 58th FOCS, pp. 121–131. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.20]

[27]   Pavel Hrubeš and Pavel Pudlák: A note on monotone real circuits. Information Processing Letters, 131:15–19, 2018. [doi:10.1016/j.ipl.2017.11.002, ECCC:TR17-048]

[28]   Trinh Huynh and Jakob Nordström: On the virtue of succinct proofs: Amplifying communication complexity hardness to time–space trade-offs in proof complexity. In Proc. 44th STOC, pp. 233–248. ACM Press, 2012. [doi:10.1145/2213977.2214000]

[29]   Dmitry Itsykson and Dmitry Sokolov: Lower bounds for splittings by linear combinations. In Proc. 39th Math. Found. Comp. Sci. (MFCS’14), pp. 372–383. Springer, 2014. [doi:10.1007/978-3-662-44465-8_32]

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

[31]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Volume 27 of Algorithms and Combinatorics. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

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

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

[34]   Jan Krajíček: Discretely ordered modules as a first-order extension of the cutting planes proof system. J. Symbolic Logic, 63(4):1582–1596, 1998. [doi:10.2307/2586668]

[35]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511574948]

[36]   László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson: Search problems in the decision tree model. SIAM J. Discr. Math., 8(1):119–132, 1995. [doi:10.1137/S0895480192233867]

[37]   Ketan Mulmuley: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101–104, 1987. [doi:10.1007/BF02579205]

[38]   Pavel Pudlák: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symbolic Logic, 62(3):981–998, 1997. [doi:10.2307/2275583]

[39]   Pavel Pudlák: Proofs as games. Amer. Math. Monthly, 107(6):541–550, 2000. [doi:10.2307/2589349]

[40]   Pavel Pudlák: On extracting computations from propositional proofs (a survey). In Proc. 30th Found. Software Techn. Theoret. Comp. Sci. (FSTTCS’10), pp. 30–41. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010. [doi:10.4230/LIPIcs.FSTTCS.2010.30]

[41]   Anup Rao and Amir Yehudayoff: Communication Complexity and Applications. Cambridge Univ. Press, 2020. [doi:10.1017/9781108671644]

[42]   Ran Raz and Pierre McKenzie: Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999. [doi:10.1007/s004930050062]

[43]   Ran Raz and Iddo Tzameret: Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Logic, 155(3):194–224, 2008. [doi:10.1016/j.apal.2008.04.001]

[44]   Alexander A. Razborov: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Math., 31(4):354–357, 1985. Link at Math-Net.ru.

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

[46]   Alexander A. Razborov: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya Math., (1):205–227, 1995. Link at Math-Net.ru.

[47]   Alexander A. Razborov: On small size approximation models. In The Mathematics of Paul Erdös I, pp. 385–392. Springer, 1997. [doi:10.1007/978-3-642-60408-9_28]

[48]   Alexander A. Razborov: A new kind of tradeoffs in propositional proof complexity. J. ACM, 63(2):16:1–16:14, 2016. [doi:10.1145/2858790]

[49]   Alexander A. Razborov: Proof complexity and beyond. SIGACT News, 47(2):66–86, 2016. [doi:10.1145/2951860.2951875]

[50]   Benjamin Rossman: The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014. [doi:10.1137/110839059]

[51]   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]

[52]   Dmitry Sokolov: Dag-like communication and its applications. In Proc. 12th Comp. Sci. Symp. in Russia (CSR’17), pp. 294–307. Springer, 2017. [doi:10.1007/978-3-319-58747-9_26]

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

[54]   Alasdair Urquhart: Hard examples for resolution. J. ACM, 34(1):209–219, 1987. [doi:10.1145/7531.8928]

[55]   Avi Wigderson: The fusion method for lower bounds in circuit complexity. In Combinatorics, Paul Erdʺo  s is Eighty, pp. 453–468. János Bolyai Math. Soc., Budapest, 1993.

[56]   Xiaodi Wu, Penghui Yao, and Henry Yuen: Raz–McKenzie simulation with the inner product gadget. Electron. Colloq. Comput. Complexity, TR17-010, 2017. [ECCC]