{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T21:30:54Z","timestamp":1782941454456,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384248","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"68-77","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Automating cutting planes is NP-hard"],"prefix":"10.1145","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sajin","family":"Koroth","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"Mertz","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada \/ Institute for Advanced Study at Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[ABMP01] Michael Alekhnovich Sam Buss Shlomo Moran and Toniann Pitassi.  [ABMP01] Michael Alekhnovich Sam Buss Shlomo Moran and Toniann Pitassi."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/2694916"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.025"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00038"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/06066850X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"e_1_3_2_1_7_1","unstructured":"[BDG+04] Maria Luisa Bonet Carlos Domingo Ricard Gavald\u00e0 Alexis Maciel and Toniann Pitassi. Non-automatizability of bounded-depth Frege proofs.  [BDG+04] Maria Luisa Bonet Carlos Domingo Ricard Gavald\u00e0 Alexis Maciel and Toniann Pitassi. Non-automatizability of bounded-depth Frege proofs."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0183-5"},{"key":"e_1_3_2_1_9_1","unstructured":"[BEGJ00] Maria Luisa Bonet Juan Luis Esteban Nicola Galesi and Jan Johannsen.  [BEGJ00] Maria Luisa Bonet Juan Luis Esteban Nicola Galesi and Jan Johannsen."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352474"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275569"},{"key":"e_1_3_2_1_12_1","first-page":"254","volume-title":"Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS)","author":"Bonet Maria Luisa","year":"1997","unstructured":"[BPR97b] Maria Luisa Bonet , Toniann Pitassi , and Ran Raz . No feasible interpolation for TC0-frege proofs . In Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS) , pages 254 - 263 , 1997 . doi: 10.1109\/SFCS. 10.1109\/SFCS [BPR97b] Maria Luisa Bonet, Toniann Pitassi, and Ran Raz. No feasible interpolation for TC0-frege proofs. In Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS), pages 254-263, 1997. doi: 10.1109\/SFCS."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798353230"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580858"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_14"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_14"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.40"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000086"},{"key":"e_1_3_2_1_26_1","unstructured":"[FPPR17] Noah Fleming Denis Pankratov Toniann Pitassi and Robert Robere.  [FPPR17] Noah Fleming Denis Pankratov Toniann Pitassi and Robert Robere."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS)","author":"Random","year":"2017","unstructured":"Random CNFs are hard for cutting planes . In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS) , 2017 . doi:10. Random CNFs are hard for cutting planes. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), 2017. doi:10."},{"key":"e_1_3_2_1_28_1","first-page":"37","volume-title":"Proceedings of the 44th Mathematical Foundations of Computer Science (MFCS)","volume":"138","author":"Garl\u00edk Michal","year":"2019","unstructured":"[Gar19] Michal Garl\u00edk . Resolution lower bounds for refutation statements . In Proceedings of the 44th Mathematical Foundations of Computer Science (MFCS) , volume 138 , pages 37 : 1-37 : 13, 2019 . doi: 10.4230\/LIPIcs.MFCS. 10.4230\/LIPIcs.MFCS [Gar19] Michal Garl\u00edk. Resolution lower bounds for refutation statements. In Proceedings of the 44th Mathematical Foundations of Computer Science (MFCS), volume 138, pages 37 : 1-37 : 13, 2019. doi: 10.4230\/LIPIcs.MFCS."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188838"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188838"},{"key":"e_1_3_2_1_31_1","volume-title":"Automating Cutting Planes is NP-Hard. Electronic Colloquium on Computational Complexity (ECCC)","author":"G\u00f6\u00f6s Mika","year":"2020","unstructured":"[GKMP20] Mika G\u00f6\u00f6s , Sajin Koroth , Ian Mertz , and Toniann Pitassi . Automating Cutting Planes is NP-Hard. Electronic Colloquium on Computational Complexity (ECCC) , 2020 . URL : https:\/\/eccc.weizmann.ac.il\/report\/ 2020\/049\/. [GKMP20] Mika G\u00f6\u00f6s, Sajin Koroth, Ian Mertz, and Toniann Pitassi. Automating Cutting Planes is NP-Hard. Electronic Colloquium on Computational Complexity (ECCC), 2020. URL: https:\/\/eccc.weizmann.ac.il\/report\/ 2020\/049\/."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.38"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9195-5"},{"key":"e_1_3_2_1_34_1","first-page":"1778","volume":"47","author":"G\u00f6\u00f6s Mika","unstructured":"[GP18] Mika G\u00f6\u00f6s and Toniann Pitassi . Communication lower bounds via critical block sensitivity. SIAM Journal on Computing , 47 ( 5 ): 1778 - 1806 , 2018. [GP18] Mika G\u00f6\u00f6s and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47 ( 5 ): 1778-1806, 2018.","journal-title":"Computing"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082007"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_3_2_1_38_1","first-page":"132","volume-title":"Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS)","author":"G\u00f6\u00f6s Mika","year":"2017","unstructured":"[GPW17] Mika G\u00f6\u00f6s , Toniann Pitassi , and Thomas Watson . Query-tocommunication lifting for BPP . In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS) , pages 132 - 143 , 2017 . [GPW17] Mika G\u00f6\u00f6s, Toniann Pitassi, and Thomas Watson. Query-tocommunication lifting for BPP. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), pages 132-143, 2017."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1617"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.20"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.11.002"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029974"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2674"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19980440403"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.81"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192233867"},{"key":"e_1_3_2_1_51_1","first-page":"84","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"132","author":"Mertz Ian","unstructured":"[MPW19] Ian Mertz , Toniann Pitassi , and Yuanhao Wei . Short proofs are hard to ifnd . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , volume 132 , pages 84 : 1-84 : 16. [MPW19] Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short proofs are hard to ifnd. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 84 : 1-84 : 16."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.84"},{"key":"e_1_3_2_1_53_1","unstructured":"[O'D17] Ryan O'Donnell. SOS is not obviously automatizable even approximately.  [O'D17] Ryan O'Donnell. SOS is not obviously automatizable even approximately."},{"key":"e_1_3_2_1_54_1","first-page":"59","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"67","author":"In","year":"2017","unstructured":"In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) , volume 67 , pages 59 : 1-59 : 10. Schloss Dagstuhl , 2017 . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), volume 67, pages 59 : 1-59 : 10. Schloss Dagstuhl, 2017."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.2307\/2589349"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2010.30"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1070\/IM1995v059n01ABEH000009"},{"key":"e_1_3_2_1_60_1","unstructured":"[RM99] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy.  [RM99] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050062"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.80"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58747-9_26"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":62,"alternative-id":["10.1145\/3357713.3384248","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384248","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}