{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:04Z","timestamp":1725795904899},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_84","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"1015-1026","source":"Crossref","is-referenced-by-count":1,"title":["Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem"],"prefix":"10.1007","author":[{"given":"Iddo","family":"Tzameret","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"84_CR1","unstructured":"Achlioptas, D.: Random satisfiability. In: Handbook of Satisfiability, pp. 245\u2013270 (2009)"},{"issue":"4","key":"84_CR2","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1137\/06066850X","volume":"38","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Razborov, A.A.: Resolution is not automatizable unless W[P] is tractable. SIAM J. Comput.\u00a038(4), 1347\u20131363 (2008)","journal-title":"SIAM J. Comput."},{"key":"84_CR3","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. Information and Computation\u00a0189, 182\u2013201 (2004)","journal-title":"Information and Computation"},{"key":"84_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-642-14165-2_10","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2010","unstructured":"Atserias, A., Maneva, E.: Mean-payoff games and propositional proofs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 102\u2013113. Springer, Heidelberg (2010)"},{"key":"84_CR5","unstructured":"Beckmann, A., Pudl\u00e1k, P., Thapen, N.: Parity games and propositional proofs. ACM Transactions on Computational Logic (to appear)"},{"issue":"3","key":"84_CR6","doi-asserted-by":"publisher","first-page":"708","DOI":"10.2307\/2275569","volume":"62","author":"M.L. Bonet","year":"1997","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic\u00a062(3), 708\u2013728 (1997)","journal-title":"The Journal of Symbolic Logic"},{"issue":"6","key":"84_CR7","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/S0097539798353230","volume":"29","author":"M.L. Bonet","year":"2000","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: On interpolation and automatization for Frege systems. SIAM J. Comput.\u00a029(6), 1939\u20131967 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"84_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1017\/S096354830600784X","volume":"16","author":"A. Coja-Oghlan","year":"2007","unstructured":"Coja-Oghlan, A., Goerdt, A., Lanka, A.: Strong refutation heuristics for random k-SAT. Combinatorics, Probability & Computing\u00a016(1), 5\u201328 (2007)","journal-title":"Combinatorics, Probability & Computing"},{"key":"84_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Turan, G.: On the complexity of cutting plane proofs. Discrete Applied Mathematics\u00a018, 25\u201338 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"84_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: STOC, pp. 534\u2013543 (2002)","DOI":"10.1145\/509984.509985"},{"key":"84_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U.: Refuting smoothed 3CNF formulas. In: Proceedings of the IEEE 48th Annual Symposium on Foundations of Computer Science, pp. 407\u2013417. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.16"},{"key":"84_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U., Kim, J.H., Ofek, E.: Witnesses for non-satisfiability of dense random 3CNF formulas. In: Proceedings of the IEEE 47th Annual Symposium on Foundations of Computer Science (2006)","DOI":"10.1109\/FOCS.2006.78"},{"issue":"1","key":"84_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.4086\/toc.2007.v003a002","volume":"3","author":"U. Feige","year":"2007","unstructured":"Feige, U., Ofek, E.: Easily refutable subformulas of large random 3CNF formulas. Theory of Computing\u00a03(1), 25\u201343 (2007)","journal-title":"Theory of Computing"},{"issue":"2","key":"84_CR14","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1137\/S009753970444096X","volume":"35","author":"J. Friedman","year":"2005","unstructured":"Friedman, J., Goerdt, A., Krivelevich, M.: Recognizing more unsatisfiable random k-SAT instances efficiently. SIAM J. Comput.\u00a035(2), 408\u2013430 (2005)","journal-title":"SIAM J. Comput."},{"key":"84_CR15","doi-asserted-by":"crossref","unstructured":"Goerdt, A., Krivelevich, M.: Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In: Annual Symposium on Theoretical Aspects of Computer Science, pp. 294\u2013304 (2001)","DOI":"10.1007\/3-540-44693-1_26"},{"key":"84_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S1571-0653(04)00461-5","volume":"16","author":"A. Goerdt","year":"2003","unstructured":"Goerdt, A., Lanka, A.: Recognizing more random unsatisfiable 3-SAT instances efficiently. Electronic Notes in Discrete Mathematics\u00a016, 21\u201346 (2003)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"84_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-642-22006-7_51","volume-title":"Automata, Languages and Programming","author":"L. Huang","year":"2011","unstructured":"Huang, L., Pitassi, T.: Automatizability and simple stochastic games. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 605\u2013617. Springer, Heidelberg (2011)"},{"issue":"1","key":"84_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"Kraj\u00ed\u010dek, J.: Lower bounds to the size of constant-depth propositional proofs. The Journal of Symbolic Logic\u00a059(1), 73\u201386 (1994)","journal-title":"The Journal of Symbolic Logic"},{"issue":"2","key":"84_CR19","first-page":"457","volume":"62","author":"J. Kraj\u00ed\u010dek","year":"1997","unstructured":"Kraj\u00ed\u010dek, J.: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Jour.\u00a0Symb.\u00a0Logic\u00a062(2), 457\u2013486 (1997)","journal-title":"Jour.\u00a0Symb.\u00a0Logic"},{"issue":"1-2","key":"84_CR20","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-2), 123\u2013140 (2001)","journal-title":"Fund. Math."},{"issue":"1","key":"84_CR21","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/inco.1997.2674","volume":"140","author":"J. Kraj\u00ed\u010dek","year":"1998","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Some consequences of cryptographical conjectures for S1\n                  2 and EF. Inform. and Comput.\u00a0140(1), 82\u201394 (1998)","journal-title":"Inform. and Comput."},{"key":"84_CR22","doi-asserted-by":"crossref","unstructured":"M\u00fcller, S., Tzameret, I.: Short propositional refutations for dense random 3CNF formulas. In: Proceedings of the 27th Annual ACM-IEEE Symposium on Logic In Computer Science (LICS) (2012)","DOI":"10.1109\/LICS.2012.60"},{"issue":"3","key":"84_CR23","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. The Journal of Symbolic Logic\u00a062(3), 981\u2013998 (1997)","journal-title":"The Journal of Symbolic Logic"},{"key":"84_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(02)00411-5","volume":"295","author":"P. Pudl\u00e1k","year":"2003","unstructured":"Pudl\u00e1k, P.: On reducibility and symmetry of disjoint NP pairs. Theoret. Comput. Sci.\u00a0295, 323\u2013339 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"84_CR25","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.apal.2008.04.001","volume":"155","author":"R. Raz","year":"2008","unstructured":"Raz, R., Tzameret, I.: Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Logic\u00a0155(3), 194\u2013224 (2008)","journal-title":"Ann. Pure Appl. Logic"},{"key":"84_CR26","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On provably disjoint NP-pairs. ECCC\u00a01(6) (1994)","DOI":"10.7146\/brics.v1i36.21607"},{"issue":"1","key":"84_CR27","first-page":"201","volume":"59","author":"A.A. Razborov","year":"1995","unstructured":"Razborov, A.A.: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izv. Ross. Akad. Nauk Ser. Mat.\u00a059(1), 201\u2013224 (1995)","journal-title":"Izv. Ross. Akad. Nauk Ser. Mat."},{"key":"84_CR28","unstructured":"Tzameret, I.: Sparser random 3-SAT refutation algorithms and the interpolation problem (2014), \n                    \n                      http:\/\/arxiv.org\/abs\/1305.0948"}],"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-662-43948-7_84","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:04:57Z","timestamp":1558922697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}