{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:00:03Z","timestamp":1748462403524,"version":"3.28.0"},"reference-count":20,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181983","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"593-603","source":"Crossref","is-referenced-by-count":25,"title":["Satisfiability, branch-width and Tseitin tautologies"],"prefix":"10.1109","author":[{"given":"M.","family":"Alekhnovich","sequence":"first","affiliation":[]},{"given":"A.A.","family":"Razborov","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237979"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798353230"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"11","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"bodlaender","year":"1993","journal-title":"Acta Cybernetica"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814614"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959893"},{"key":"20","article-title":"On the complexity of derivations in propositional calculus","author":"tseitin","year":"1968","journal-title":"Studies in Constructive Mathematics and Mathematical Logic part II"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892064"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00395-5"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"7","article-title":"On the automatizability of resolution and related propositional proof systems","author":"atserias","year":"2002","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00331-2"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959895"},{"key":"9","first-page":"415","article-title":"Random CNF's are hard for the polynomial calculus","author":"ben-sasson","year":"1999","journal-title":"Proceedings of the 40th IEEE FOCS"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548486"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","acronym":"SFCS-02","location":"Vancouver, BC, Canada"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181983.pdf?arnumber=1181983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T23:31:51Z","timestamp":1489447911000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181983\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":20,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181983","relation":{},"subject":[]}}