{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:29:42Z","timestamp":1725542982010},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540372066"},{"type":"electronic","value":"9783540372073"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11814948_3","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T06:12:38Z","timestamp":1153203158000},"page":"11-21","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of Semialgebraic Proofs with Restricted Degree of Falsity"],"prefix":"10.1007","author":[{"given":"Arist","family":"Kojevnikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"3_CR1","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The Relative Efficiency of Propositional Proof Systems. The Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BFb0023762","volume-title":"Computer Science Logic","author":"A. Goerdt","year":"1992","unstructured":"Goerdt, A.: The Cutting Plane Proof System with Bounded Degree of Falsity. In: Kleine B\u00fcning, H., J\u00e4ger, G., B\u00f6rger, E., Richter, M.M. (eds.) CSL 1991. LNCS, vol.\u00a0626, pp. 119\u2013133. Springer, Heidelberg (1992)"},{"key":"3_CR3","first-page":"77","volume":"3","author":"J.A. Robinson","year":"1968","unstructured":"Robinson, J.A.: The generalized resolution principle. Machine Intelligence\u00a03, 77\u201394 (1968)","journal-title":"Machine Intelligence"},{"issue":"1-3","key":"3_CR4","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. Fundamenta Mathematic\u00e6\u00a0170(1-3), 123\u2013140 (2001)","journal-title":"Fundamenta Mathematic\u00e6"},{"key":"3_CR5","first-page":"269","volume-title":"Recent Advances in Mathematical Programming","author":"R.E. Gomory","year":"1963","unstructured":"Gomory, R.E.: An algorithm for integer solutions of linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269\u2013302. McGraw-Hill, New York (1963)"},{"issue":"1","key":"3_CR6","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., Tur\u00e1n, G.: On the complexity of cutting-plane proofs. Discrete Applied Mathematics\u00a018(1), 25\u201338 (1987)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"3_CR7","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","volume":"2","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semialgebraic proofs. Moscow Mathematical Journal\u00a02(4), 647\u2013679 (2002)","journal-title":"Moscow Mathematical Journal"},{"issue":"2","key":"3_CR8","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(2), 182\u2013201 (2004)","journal-title":"Information and Computation"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/11499107_10","volume-title":"Theory and Applications of Satisfiability Testing","author":"E.A. Hirsch","year":"2005","unstructured":"Hirsch, E.A., Nikolenko, S.I.: Simulating Cutting Plane proofs with restricted degree of falsity by Resolution. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 135\u2013142. Springer, Heidelberg (2005)"},{"issue":"5","key":"3_CR10","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. SIAM Journal on Computing\u00a033(5), 1171\u20131200 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0097539701389944","volume":"34","author":"M. Alekhnovich","year":"2004","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. SIAM Journal on Computing\u00a034(1), 67\u201388 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/1060590.1060628","volume-title":"STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M.: Lower bounds for k-DNF resolution on random 3-CNFs. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 251\u2013256. ACM Press, New York (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814948_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:28:01Z","timestamp":1619494081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814948_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540372066","9783540372073"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/11814948_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}