{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:02:14Z","timestamp":1787508134592,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488711","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T12:35:41Z","timestamp":1369744541000},"page":"813-822","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Some trade-off results for polynomial calculus"],"prefix":"10.1145","author":[{"given":"Chris","family":"Beck","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakob","family":"Nordstrom","sequence":"additional","affiliation":[{"name":"KTH Institute of Royal Technology, Stockholm, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bangsheng","family":"Tang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366735"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0028-y"},{"key":"e_1_3_2_1_3_1","first-page":"18","article-title":"Lower bounds for polynomial calculus: Non-binomial case","volume":"242","author":"Alekhnovich M.","year":"2003","unstructured":"M. Alekhnovich and A. A. Razborov . Lower bounds for polynomial calculus: Non-binomial case . In Proc. Steklov Institute of Mathematics , 242 : 18 -- 35 , 2003 . M. Alekhnovich and A. A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. In Proc. Steklov Institute of Mathematics, 242:18--35, 2003.","journal-title":"Proc. Steklov Institute of Mathematics"},{"key":"e_1_3_2_1_4_1","volume-title":"ECCC","author":"Allender E.","year":"2012","unstructured":"E. Allender , S. Chen , T. Lou , P. Papakonstantinou , and B. Tang . Width-parameterized SAT: Time-space tradeoffs. TR12-027 , ECCC , 2012 . E. Allender, S. Chen, T. Lou, P. Papakonstantinou, and B. Tang. Width-parameterized SAT: Time-space tradeoffs. TR12-027, ECCC, 2012."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.025"},{"key":"e_1_3_2_1_6_1","first-page":"203","volume-title":"Proc. 14th National Conference on Artificial Intelligence","author":"Bayardo R. J.","year":"1997","unstructured":"R. J. Bayardo Jr . and R. Schrag . Using CSP look-back techniques to solve real-world SAT instances . In Proc. 14th National Conference on Artificial Intelligence , pp. 203 -- 208 , 1997 . R. J. Bayardo Jr. and R. Schrag. Using CSP look-back techniques to solve real-world SAT instances. In Proc. 14th National Conference on Artificial Intelligence, pp. 203--208, 1997."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"P.\n      Beame\n    .\n  Proof complexity. Computational Complexity Theory volume \n  10\n   of \n  IAS\/Park City Mathematics Series pp. \n  199\n  --\n  246 2004\n  .  P. Beame. Proof complexity. Computational Complexity Theory volume 10 of IAS\/Park City Mathematics Series pp. 199--246 2004.","DOI":"10.1090\/pcms\/010\/07"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213999"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875477"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/080723880"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10089"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.42"},{"key":"e_1_3_2_1_13_1","first-page":"401","volume-title":"Proc. 2nd Symposium on Innovations in Computer Science","author":"Ben-Sasson E.","year":"2011","unstructured":"E. Ben-Sasson and J. Nordstr\u00f6m . Understanding space in proof complexity: Separations and trade-offs via substitutions . In Proc. 2nd Symposium on Innovations in Computer Science , pp. 401 -- 416 , 2011 . E. Ben-Sasson and J. Nordstr\u00f6m. Understanding space in proof complexity: Separations and trade-offs via substitutions. In Proc. 2nd Symposium on Innovations in Computer Science, pp. 401--416, 2011."},{"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","series-title":"FAIA","volume-title":"Handbook of Satisfiability","author":"Biere A.","year":"2009","unstructured":"A. Biere , M. J. H. Heule , H. van Maaren , and T. Walsh , editors . Handbook of Satisfiability , vol. 185 of FAIA . IOS Press , 2009 . A. Biere, M. J. H. Heule, H. van Maaren, and T. Walsh, editors. Handbook of Satisfiability, vol. 185 of FAIA. IOS Press, 2009."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422486"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2008.02.017"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1726"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80048-7"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2921"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.27"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214000"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/244522.244560"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.06.006"},{"key":"e_1_3_2_1_33_1","volume-title":"Pebble games, proof complexity and time-space trade-offs. Log. Meth. Comput. Sci., to appear","author":"Nordstr\u00f6m J.","year":"2013","unstructured":"J. Nordstr\u00f6m . Pebble games, proof complexity and time-space trade-offs. Log. Meth. Comput. Sci., to appear , 2013 . J. Nordstr\u00f6m. Pebble games, proof complexity and time-space trade-offs. Log. Meth. Comput. Sci., to appear, 2013."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972640"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00453-X"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1203350879"},{"key":"e_1_3_2_1_41_1","first-page":"115","article-title":"On the complexity of derivation in propositional calculus. In Structures in Constructive Mathematics and mathematical Logic","author":"Tseitin G.","year":"1968","unstructured":"G. Tseitin . On the complexity of derivation in propositional calculus. In Structures in Constructive Mathematics and mathematical Logic , Part II , pp. 115 -- 125 , 1968 . G. Tseitin. On the complexity of derivation in propositional calculus. In Structures in Constructive Mathematics and mathematical Logic, Part II, pp. 115--125, 1968.","journal-title":"Part II"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488711","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:21Z","timestamp":1750221561000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488711"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":41,"alternative-id":["10.1145\/2488608.2488711","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488711","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}