{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T10:15:12Z","timestamp":1729678512437,"version":"3.28.0"},"reference-count":56,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1109\/ccc.2014.36","type":"proceedings-article","created":{"date-parts":[[2014,8,20]],"date-time":"2014-08-20T15:19:59Z","timestamp":1408547999000},"page":"286-297","source":"Crossref","is-referenced-by-count":6,"title":["Narrow Proofs May Be Maximally Long"],"prefix":"10.1109","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[]},{"given":"Jakob","family":"Nordstrom","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"35","first-page":"269","article-title":"An algorithm for integer solutions of linear programs","author":"gomory","year":"1963","journal-title":"Recent Advances in Mathematical Programming"},{"key":"36","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"34","doi-asserted-by":"publisher","DOI":"10.1137\/0206031"},{"key":"39","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"37","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45841-7_34"},{"key":"38","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","article-title":"Complexity of semialgebraic proofs","volume":"2","author":"grigoriev","year":"2002","journal-title":"Moscow Mathematical Journal"},{"key":"43","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"key":"42","article-title":"Computational limitations of small-depth circuits","author":"hastad","year":"1987","journal-title":"Massachussetts Institute of Technology"},{"key":"41","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"40","doi-asserted-by":"crossref","DOI":"10.1145\/2591796.2591838","article-title":"Communication lower bounds via critical block sensiti vity","author":"goos","year":"2014","journal-title":"Proc 46th Annual ACM Symposium on Theory of Computing (STOC ?14)"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2008.11.043"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.002"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.025"},{"key":"2","first-page":"18","article-title":"Lower bounds for polynomial calculus: Non-binomial case","volume":"242","author":"alekhnovich","year":"2003","journal-title":"Proc Steklov Institute of Mathematics"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366735"},{"key":"7","first-page":"203","article-title":"Using CSP look-back techniques to solve real-world SAT instances","author":"bayardo jr","year":"1997","journal-title":"Proc 14th National Conference on Artificial Intelligence (AAAI ?97)"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2921"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.20"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.27"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02777-2_13"},{"key":"31","first-page":"437","article-title":"Towards an understanding of polynomial calculus: New separations and lower bounds (extended abstract)","volume":"7965","author":"filmus","year":"2013","journal-title":"Proc 40th International Colloquium on Automata Languages and Programming (ICALP ? 13) Ser Lecture Notes in Computer Science"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1137\/060654645"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213999"},{"key":"56","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"},{"journal-title":"Canonical expressions in Boolean algebra","year":"1937","author":"blake","key":"19"},{"key":"55","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1145\/2499937.2499941"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1145\/2355580.2355582"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.48"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.42"},{"key":"14","first-page":"401","article-title":"Understanding space in proof complexity: Separations and trade-offs via substitutions","author":"ben-sasson","year":"2011","journal-title":"Proc 2nd Symposium on Innovations in Computer Science (ICS ?11)"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1137\/080723880"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10089"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2008.02.017"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422486"},{"key":"49","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.111"},{"key":"48","doi-asserted-by":"publisher","DOI":"10.1109\/DAC.2001.156196"},{"key":"45","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","article-title":"A comparison of the Sherali-Adams, Lovas? z-Schrijver and Lasserre relaxations for 0-1 programming","volume":"28","author":"laurent","year":"2001","journal-title":"Mathematics of Operations Research"},{"key":"44","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","article-title":"An explicit exact SDP relaxation for nonlinear 0-1 programs","volume":"2081","author":"lasserre","year":"2001","journal-title":"Proc 8th International Conference on Integer Programming and Combinatorial Optimization Ser Lecture Notes in Computer Science"},{"key":"47","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1109\/12.769433","article-title":"GRASP: A search algorithm for propositional satisfiability","volume":"48","author":"marques-silva","year":"1999","journal-title":"IEEE Transactions on Computers"},{"key":"46","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488711"},{"key":"51","first-page":"197","article-title":"On the compl exity of propositional calculus","volume":"258","author":"pudlak","year":"1999","journal-title":"Sets and Proofs Ser London Mathematical Society Lecture Note Series"},{"key":"52","doi-asserted-by":"publisher","DOI":"10.2307\/2589349"},{"key":"53","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"54","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"50","article-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization","author":"parrilo","year":"2000","journal-title":"California Institute of Technology"}],"event":{"name":"2014 IEEE Conference on Computational Complexity (CCC)","start":{"date-parts":[[2014,6,11]]},"location":"Vancouver, BC, Canada","end":{"date-parts":[[2014,6,13]]}},"container-title":["2014 IEEE 29th Conference on Computational Complexity (CCC)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/6875457\/6875460\/06875497.pdf?arnumber=6875497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T00:37:25Z","timestamp":1565743045000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/6875497\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":56,"URL":"https:\/\/doi.org\/10.1109\/ccc.2014.36","relation":{},"subject":[],"published":{"date-parts":[[2014,6]]}}}