{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:45Z","timestamp":1725856965788},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319398167"},{"type":"electronic","value":"9783319398174"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-39817-4_26","type":"book-chapter","created":{"date-parts":[[2016,5,26]],"date-time":"2016-05-26T09:15:09Z","timestamp":1464254109000},"page":"269-278","source":"Crossref","is-referenced-by-count":0,"title":["On the Lower Bounds of Random Max 3 and 4-SAT"],"prefix":"10.1007","author":[{"given":"Guangyan","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,27]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Moore, C.: The asymptotic order of the random k-SAT threshold. In: Proceedings of 43rd Annual Symposium on Foundations of Computer Science, pp. 126\u2013127 (2002)","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Naor, A., Peres, Y.: On the maximum satisfiability of random formulas. J. Assoc. Comput. Machinary 54(2) (2007)","DOI":"10.1145\/1219092.1219098"},{"issue":"4","key":"26_CR3","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1090\/S0894-0347-04-00464-3","volume":"17","author":"D Achlioptas","year":"2004","unstructured":"Achlioptas, D., Peres, Y.: The threshold for random $$k$$ -SAT is $$2^k\\log 2-O(k)$$ . J. Am. Math. Soc. 17(4), 947\u2013973 (2004)","journal-title":"J. Am. Math. Soc."},{"issue":"4","key":"26_CR4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1009725216438","volume":"2","author":"B Borchers","year":"1998","unstructured":"Borchers, B., Furman, J.: A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems. J. Comb. Optim. 2(4), 299\u2013306 (1998)","journal-title":"J. Comb. Optim."},{"key":"26_CR5","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proceedings of 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 322\u2013330 (1993)"},{"key":"26_CR6","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M.T., Sorkin, G.B.: Random MAX 2-SAT and MAX CUT. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD). ACM, New York (2003)"},{"key":"26_CR7","volume-title":"Asymptotic Methods in Analysis","author":"NG Bruijn de","year":"1981","unstructured":"de Bruijn, N.G.: Asymptotic Methods in Analysis, 3rd edn. Dover Publications Inc., New York (1981)","edition":"3"},{"key":"26_CR8","unstructured":"Fernandez de la Vega, W., Karpinski, M.: $$9\/8$$ -approximation algorithm for random max 3-sat. Technical Report TR02-070, Electronic Colloquium on Computational Complexity (2002)"},{"key":"26_CR9","unstructured":"Gao, Z., Liu, J., Xu, K.: A novel weighting scheme for random $$k$$ -SAT. arXiv:1310.4303"},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M Goemans","year":"1994","unstructured":"Goemans, M., Williamson, D.: New $$3\/4$$ -approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7, 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"26_CR11","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-46541-3_5","volume-title":"STACS 2000","author":"EA Hirsch","year":"2000","unstructured":"Hirsch, E.A.: A new algorithm for MAX-2-SAT. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, p. 65. Springer, Heidelberg (2000)"},{"issue":"3","key":"26_CR13","first-page":"287","volume":"17","author":"FY Vorob\u2019ev","year":"2007","unstructured":"Vorob\u2019ev, F.Y.: A lower bound for the 4-satisfiability threshold. Discrete Math. Appl. 17(3), 287\u2013294 (2007)","journal-title":"Discrete Math. Appl."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-39817-4_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T11:06:01Z","timestamp":1498302361000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-39817-4_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319398167","9783319398174"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-39817-4_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}