{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:26:27Z","timestamp":1775571987101,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":77,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188838","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"902-911","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Monotone circuit lower bounds from resolution"],"prefix":"10.1145","author":[{"given":"Ankit","family":"Garg","sequence":"first","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}]},{"given":"Pritish","family":"Kamath","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Dmitry","family":"Sokolov","sequence":"additional","affiliation":[{"name":"KTH, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Noga Alon and Ravi Boppana. 1987. Noga Alon and Ravi Boppana. 1987."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138445X"},{"key":"e_1_3_2_2_4_1","unstructured":"Alexander Andreev. 1985. Alexander Andreev. 1985."},{"key":"e_1_3_2_2_5_1","volume-title":"Doklady Akademii Nauk USSR 281, 2","author":"On","year":"1985"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.025"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806703"},{"key":"e_1_3_2_2_8_1","unstructured":"Paul Beame and Toniann Pitassi. 2001. Paul Beame and Toniann Pitassi. 2001."},{"key":"e_1_3_2_2_9_1","volume-title":"Current Trends in Theoretical Computer Science: Entering the 21st Century. World Scientific, 42\u201370. 9789812810403_0001","author":"Complexity Propositional Proof"},{"key":"e_1_3_2_2_10_1","unstructured":"Paul Beame Toniann Pitassi and Nathan Segerlind. 2007. Paul Beame Toniann Pitassi and Nathan Segerlind. 2007."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654645"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_3_2_2_13_1","unstructured":"375835 375835"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050017"},{"key":"e_1_3_2_2_15_1","unstructured":"Maria Bonet Toniann Pitassi and Ran Raz. 1997. Maria Bonet Toniann Pitassi and Ran Raz. 1997."},{"key":"e_1_3_2_2_16_1","volume-title":"The Journal of Symbolic Logic 62, 3","author":"Cutting Planes Lower Bounds","year":"1997"},{"key":"e_1_3_2_2_17_1","unstructured":"Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017. Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017."},{"key":"e_1_3_2_2_18_1","unstructured":"Simulation Theorems via Pseudorandom Properties. Technical Report. arXiv. arXiv: 1704.06807 Simulation Theorems via Pseudorandom Properties. Technical Report. arXiv. arXiv: 1704.06807"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.40"},{"key":"e_1_3_2_2_21_1","unstructured":"40 40"},{"key":"e_1_3_2_2_22_1","volume-title":"Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS). Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS).","author":"Fleming Noah","year":"2017"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100001"},{"key":"e_1_3_2_2_24_1","unstructured":"Ankit Garg Mika G\u00f6\u00f6s Pritish Kamath and Dmitrt Sokolov. 2017. Ankit Garg Mika G\u00f6\u00f6s Pritish Kamath and Dmitrt Sokolov. 2017."},{"key":"e_1_3_2_2_25_1","unstructured":"Monotone Circuit Lower Bounds from Resolution. Technical Report TR17-175. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann. ac.il\/report\/2017\/175\/ Monotone Circuit Lower Bounds from Resolution. Technical Report TR17-175. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann. ac.il\/report\/2017\/175\/"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.12"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M103145X"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591838"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_3_2_2_30_1","unstructured":"2015.70 2015.70"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_3_2_2_32_1","unstructured":"To appear. To appear."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796269"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1617"},{"key":"e_1_3_2_2_35_1","unstructured":"Danny Harnik and Ran Raz. 2000. Danny Harnik and Ran Raz. 2000."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335349"},{"key":"e_1_3_2_2_37_1","unstructured":"Pavel Hrube\u0161 and Pavel Pudl\u00e1k. 2017. Pavel Hrube\u0161 and Pavel Pudl\u00e1k. 2017."},{"key":"e_1_3_2_2_38_1","unstructured":"A note on monotone real circuits. Technical Report TR17-048. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2017\/048\/ A note on monotone real circuits. Technical Report TR17-048. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2017\/048\/"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.20"},{"key":"e_1_3_2_2_40_1","unstructured":"Trinh Huynh and Jakob Nordstr\u00f6m. 2012. Trinh Huynh and Jakob Nordstr\u00f6m. 2012."},{"key":"e_1_3_2_2_41_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing (STOC). ACM, 233\u2013248","author":"Succinct Proofs On"},{"key":"e_1_3_2_2_42_1","unstructured":"Dmitry Itsykson and Dmitry Sokolov. 2014. Dmitry Itsykson and Dmitry Sokolov. 2014."},{"key":"e_1_3_2_2_43_1","volume-title":"Proceedings of the 39th Mathematical Foundations of Computer Science (MFCS)","author":"Linear Combinations Lower Bounds"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/791230.792304"},{"key":"e_1_3_2_2_45_1","unstructured":"Stasys Jukna. 2012. Stasys Jukna. 2012."},{"key":"e_1_3_2_2_46_1","volume-title":"Advances and Frontiers. Algorithms and Combinatorics","author":"Complexity Boolean Function"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62265"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586668"},{"key":"e_1_3_2_2_50_1","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Eyal Kushilevitz and Noam Nisan. 1997."},{"key":"e_1_3_2_2_51_1","unstructured":"Communication Complexity. Cambridge University Press. Communication Complexity. Cambridge University Press."},{"key":"e_1_3_2_2_52_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz Moni Naor Ilan Newman and Avi Wigderson. 1995. L\u00e1szl\u00f3 Lov\u00e1sz Moni Naor Ilan Newman and Avi Wigderson. 1995."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192233867"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2000.12005233"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k. 2010. Pavel Pudl\u00e1k. 2010.","DOI":"10.3917\/rindu.103.0074"},{"key":"e_1_3_2_2_57_1","volume-title":"Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FST TCS)","volume":"8","author":"On"},{"key":"e_1_3_2_2_58_1","unstructured":"Anup Rao and Amir Yehudayoff. 2017. Anup Rao and Amir Yehudayoff. 2017."},{"key":"e_1_3_2_2_59_1","unstructured":"Communication Complexity. In preparation. Communication Complexity. In preparation."},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796321"},{"key":"e_1_3_2_2_61_1","unstructured":"Ran Raz and Iddo Tzameret. 2008. Ran Raz and Iddo Tzameret. 2008."},{"key":"e_1_3_2_2_62_1","volume-title":"Annals of Pure and Applied Logic 155, 3","author":"Resolution","year":"2008"},{"key":"e_1_3_2_2_63_1","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"285","author":"Razborov Alexander","year":"1985","journal-title":"Doklady Akademii Nauk USSR"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73023"},{"key":"e_1_3_2_2_65_1","unstructured":"Alexander Razborov. 1995. Alexander Razborov. 1995."},{"key":"e_1_3_2_2_66_1","volume-title":"Izvestiya of the RAN","author":"Unprovability","year":"1995"},{"key":"e_1_3_2_2_67_1","unstructured":"Alexander Razborov. 1997. Alexander Razborov. 1997."},{"key":"e_1_3_2_2_68_1","unstructured":"On Small Size Approximation Models. In The Mathematics of Paul Erd\u00f6s I. Springer 385\u2013392. 978-3-642-60408-9_28 On Small Size Approximation Models. In The Mathematics of Paul Erd\u00f6s I. Springer 385\u2013392. 978-3-642-60408-9_28"},{"key":"e_1_3_2_2_69_1","unstructured":"Alexander Razborov. 2016. Alexander Razborov. 2016."},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858790"},{"key":"e_1_3_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951860.2951875"},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839059"},{"key":"e_1_3_2_2_73_1","unstructured":"Janos Simon and Shi-Chun Tsai. 1997. Janos Simon and Shi-Chun Tsai. 1997."},{"key":"e_1_3_2_2_74_1","volume-title":"Note on the Bottleneck Counting Argument. In Proceedings of the 12th Computational Complexity Conference (CCC). 297\u2013301","author":"A"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58747-9_26"},{"key":"e_1_3_2_2_76_1","volume-title":"Combinatorics, Paul Erd\u0151s is Eighty","author":"Wigderson Avi"},{"key":"e_1_3_2_2_77_1","unstructured":"Xiaodi Wu Penghui Yao and Henry Yuen. 2017. Xiaodi Wu Penghui Yao and Henry Yuen. 2017."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188838","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T07:04:39Z","timestamp":1751699079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":77,"alternative-id":["10.1145\/3188745.3188838","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188838","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}