{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:00Z","timestamp":1750694700865,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"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":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806703","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"87-96","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Hardness amplification in proof complexity"],"prefix":"10.1145","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Trinh","family":"Huynh","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1328865.1328873"},{"key":"e_1_3_2_1_3_1","volume-title":"50th IEEE FOCS, 53--62","author":"Beame P.","year":"2009","unstructured":"P. Beame and D.--T. Huynh-- Ngoc . Multiparty communication complexity and threshold circuit size of AC0 . In 50th IEEE FOCS, 53--62 , 2009 . P. Beame and D.--T. Huynh--Ngoc. Multiparty communication complexity and threshold circuit size of AC0. In 50th IEEE FOCS, 53--62, 2009."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_3_2_1_5_1","volume-title":"44th IEEE FOCS, 318--327","author":"Buresh-Oppenheim J.","year":"2003","unstructured":"J. Buresh-Oppenheim , N. Galesi , S. Hoory , A. Magen , and T. Pitassi . Rank bounds and integrality gaps for cutting planes procedures . In 44th IEEE FOCS, 318--327 , 2003 . J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi. Rank bounds and integrality gaps for cutting planes procedures. In 44th IEEE FOCS, 318--327, 2003."},{"key":"e_1_3_2_1_6_1","volume-title":"ECCC","author":"Buresh-Oppenheim J.","year":"2006","unstructured":"J. Buresh-Oppenheim and R. Santhanam . Making hard problems harder. TR06-03 , ECCC , 2006 . J. Buresh-Oppenheim and R. Santhanam. Making hard problems harder. TR06-03, ECCC, 2006."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_1_8_1","volume-title":"ECCC","author":"Chattopadhyay A.","year":"2008","unstructured":"A. Chattopadhyay and A. Ada . Multiparty communication complexity of disjointness. TR08-002 , ECCC , 2008 . A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. TR08-002, ECCC, 2008."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8195-x"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.34"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_16_1","first-page":"419","article-title":"Complexity of semi-algebraic proofs","volume":"2285","author":"Grigoriev D.","year":"2002","unstructured":"D. Grigoriev , E. A. Hirsch , and D. V. Pasechnik . Complexity of semi-algebraic proofs . In STACS LNCS v. 2285 , 419 -- 430 , 2002 . D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik. Complexity of semi-algebraic proofs. In STACS LNCS v. 2285, 419--430, 2002.","journal-title":"STACS LNCS"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_18_1","volume-title":"9th IEEE LICS, 220--228","author":"Impagliazzo R.","year":"1994","unstructured":"R. Impagliazzo , T. Pitassi , and A. Urquhart . Upper and lower bounds on tree-like cutting planes proofs . In 9th IEEE LICS, 220--228 , 1994 . R. Impagliazzo, T. Pitassi, and A. Urquhart. Upper and lower bounds on tree-like cutting planes proofs. In 9th IEEE LICS, 220--228, 1994."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_29"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586668"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/264772"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645590.757890"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.29"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.19"},{"key":"e_1_3_2_1_27_1","volume-title":"Threshold logic and its applications","author":"Muroga S.","year":"1971","unstructured":"S. Muroga . Threshold logic and its applications . John Wiley & Sons , 1971 . S. Muroga. Threshold logic and its applications. John Wiley & Sons, 1971."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796321"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.2"},{"key":"e_1_3_2_1_32_1","volume-title":"ACM-SIAM SODA, 355--364","author":"Segerlind N.","year":"2009","unstructured":"N. Segerlind and T. Pitassi . Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures . In ACM-SIAM SODA, 355--364 , 2009 . N. Segerlind and T. Pitassi. Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. In ACM-SIAM SODA, 355--364, 2009."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250834"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374392"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts USA","acronym":"STOC'10"},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806703","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:36Z","timestamp":1750246776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":36,"alternative-id":["10.1145\/1806689.1806703","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806703","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}