{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:48:22Z","timestamp":1725587302296},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_54","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"642-653","source":"Crossref","is-referenced-by-count":0,"title":["On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution"],"prefix":"10.1007","author":[{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Razborov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory\u00a043, 196\u2013204 (1986)","journal-title":"J. Comb. Theory"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: Lower bounds for k-DNF resolution on random 3-CNFs. In: Proc. 37th ACM Symposium on Theory of Computing, pp. 251\u2013256 (May 2005)","DOI":"10.1145\/1060590.1060628"},{"issue":"4","key":"54_CR3","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/S0097539700366735","volume":"31","author":"M. Alekhnovich","year":"2002","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Space complexity in propositional calculus. SICOMP\u00a031(4), 1184\u20131211 (2002)","journal-title":"SICOMP"},{"issue":"2","key":"54_CR4","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.ic.2003.10.004","volume":"189","author":"A. Atserias","year":"2004","unstructured":"Atserias, A., Bonet, M.L.: On the automatizability of resolution and related propositional proof systems. Info. Comp.\u00a0189(2), 182\u2013201 (2004)","journal-title":"Info. Comp."},{"issue":"2","key":"54_CR5","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1006\/inco.2002.3114","volume":"176","author":"A. Atserias","year":"2002","unstructured":"Atserias, A., Bonet, M.L., Esteban, J.L.: Lower bounds for the weak pigeonhole principle and random formulas beyond resolution. Info. Comp.\u00a0176(2), 136\u2013152 (2002)","journal-title":"Info. Comp."},{"key":"54_CR6","first-page":"190","volume":"74","author":"S. Baumer","year":"2001","unstructured":"Baumer, S., Esteban, J.L., Tor\u00e1n, J.: Minimally unsatisfiable CNF formulas. Bulletin of the EATCS\u00a074, 190\u2013192 (2001)","journal-title":"Bulletin of the EATCS"},{"issue":"1","key":"54_CR7","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1002\/rsa.10089","volume":"23","author":"E. Ben-Sasson","year":"2003","unstructured":"Ben-Sasson, E., Galesi, N.: Space complexity of random formulae in resolution. Rand. Struc. Alg.\u00a023(1), 92\u2013109 (2003)","journal-title":"Rand. Struc. Alg."},{"key":"54_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: Short proofs be spacious: An optimal separation of space and length in resolution. In: Proc. 49th IEEE Symposium on Foundations of Computer Science, pp. 709\u2013718 (2008)","DOI":"10.1109\/FOCS.2008.42"},{"key":"54_CR9","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: A space hierarchy for k-DNF resolution. Technical Report TR09-047, Electronic Colloquium on Computational Complexity (2009)"},{"key":"54_CR10","unstructured":"Ben-Sasson, E., Nordstr\u00f6m, J.: Understanding space in proof complexity: Separations and trade-offs via substitutions. In: Proc. 2nd Symposium on Innovations in Computer Science, pp. 401\u2013416 (2011)"},{"issue":"2","key":"54_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow\u2014resolution made simple. J. ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"54_CR12","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal, V., Szemer\u00e9di, E.: Many hard examples for resolution. J. ACM\u00a035(4), 759\u2013768 (1988)","journal-title":"J. ACM"},{"issue":"2-3","key":"54_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.04.004","volume":"321","author":"J.L. Esteban","year":"2004","unstructured":"Esteban, J.L., Galesi, N., Messner, J.: On the complexity of resolution with bounded conjunctions. TCS\u00a0321(2-3), 347\u2013370 (2004)","journal-title":"TCS"},{"issue":"1-3","key":"54_CR14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek, J.: On the weak pigeonhole principle. Fund. Math.\u00a0170(1-3), 123\u2013140 (2001)","journal-title":"Fund. Math."},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: An application of matroid theory to the SAT problem. In: Proc. 15th IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)","DOI":"10.1109\/CCC.2000.856741"},{"issue":"1","key":"54_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/060668250","volume":"39","author":"J. Nordstr\u00f6m","year":"2009","unstructured":"Nordstr\u00f6m, J.: Narrow proofs be spacious: Separating space and width in resolution. SICOMP\u00a039(1), 59\u2013121 (2009)","journal-title":"SICOMP"},{"key":"54_CR17","unstructured":"Nordstr\u00f6m, J.: Pebble games, proof complexity and time-space trade-offs. Logical Methods in Computer Science (to appear, 2011)"},{"key":"54_CR18","doi-asserted-by":"crossref","unstructured":"Nordstr\u00f6m, J., H\u00e5stad, J.: Towards an optimal separation of space and length in resolution (Extended abstract). In: Proc. 40th ACM Symposium on Theory of Computing, pp. 701\u2013710 (May 2008)","DOI":"10.1145\/1374376.1374478"},{"key":"54_CR19","unstructured":"Razborov, A.A.: Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution (manuscript)"},{"issue":"4","key":"54_CR20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.ipl.2004.09.024","volume":"93","author":"N. Segerlind","year":"2005","unstructured":"Segerlind, N.: Exponential separation between Res(k) and Res(k\u2009+\u20091) for k\u2009\u2264\u2009\u03b5logn. IPL\u00a093(4), 185\u2013190 (2005)","journal-title":"IPL"},{"issue":"5","key":"54_CR21","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/S0097539703428555","volume":"33","author":"N. Segerlind","year":"2004","unstructured":"Segerlind, N., Buss, S.R., Impagliazzo, R.: A switching lemma for small restrictions and lower bounds for k-DNF resolution. SICOMP\u00a033(5), 1171\u20131200 (2004)","journal-title":"SICOMP"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T21:48:12Z","timestamp":1560289692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}