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 Erds 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]