{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T06:24:27Z","timestamp":1781763867071,"version":"3.54.5"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,4]]},"abstract":"\n Say that a\n k<\/jats:italic>\n -CNF a formula is\n p-satisfiable<\/jats:italic>\n if there exists a truth assignment satisfying a fraction 1 \u2212 2\n \n \u2212\n k<\/jats:italic>\n <\/jats:sup>\n +\n p<\/jats:italic>\n 2\n \n \u2212\n k<\/jats:italic>\n <\/jats:sup>\n of its clauses (note that every\n k<\/jats:italic>\n -CNF formula is 0-satisfiable). Let\n F<\/jats:italic>\n \n k<\/jats:italic>\n <\/jats:sub>\n (\n n<\/jats:italic>\n ,\n m<\/jats:italic>\n ) denote a random\n k<\/jats:italic>\n -CNF formula on\n n<\/jats:italic>\n variables with\n m<\/jats:italic>\n clauses. For every\n k<\/jats:italic>\n \u22652 and every\n r<\/jats:italic>\n >0 we determine\n p<\/jats:italic>\n and \u03b4=\u03b4(\n k<\/jats:italic>\n )=\n O<\/jats:italic>\n (\n k<\/jats:italic>\n 2\n \n \u2212\n k<\/jats:italic>\n \/2\n <\/jats:sup>\n ) such that with probability tending to 1 as\n n<\/jats:italic>\n \u2192\u221e, a random\n k<\/jats:italic>\n -CNF formula\n F<\/jats:italic>\n k<\/jats:sub>\n (\n n<\/jats:italic>\n ,\n rn<\/jats:italic>\n ) is\n p<\/jats:italic>\n -satisfiable but not (\n p<\/jats:italic>\n +\u03b4)-satisfiable.\n <\/jats:p>","DOI":"10.1145\/1219092.1219098","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["On the maximum satisfiability of random formulas"],"prefix":"10.1145","volume":"54","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[{"name":"U.C. Santa Cruz, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Assaf","family":"Naor","sequence":"additional","affiliation":[{"name":"Courant Institute, NYU"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Peres","sequence":"additional","affiliation":[{"name":"U.C. Berkeley and Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 43rd Annual Symposium on Foundations of Computer Science","author":"Achlioptas D."},{"key":"e_1_2_1_2_1","first-page":"947","article-title":"The threshold for random k-SAT is 2kln 2 − o(k)","volume":"17","author":"Achlioptas D.","year":"2004","journal-title":"J. AMS"},{"key":"e_1_2_1_3_1","unstructured":"Alon N. and Spencer J. 1991. The Probabilistic Method. Wiley New York. Alon N. and Spencer J. 1991. The Probabilistic Method. Wiley New York."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 4th Annual Symposium on Discrete Algorithms. ACM","author":"Broder A. Z."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v24:4"},{"key":"e_1_2_1_7_1","volume-title":"Asymptotic methods in analysis","author":"de Bruijn N. G."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02401841"},{"key":"e_1_2_1_9_1","first-page":"137","article-title":"Some problems concerning the structure of random walk paths. Acta Sci","volume":"11","author":"Erd\u0151s P.","year":"1960","journal-title":"Hung."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_11_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and intractability. Freeman San Francisco CA. Garey M. R. and Johnson D. S. 1979. Computers and intractability. Freeman San Francisco CA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_13_1","volume-title":"Random discrete structures, IMA","author":"Janson S."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200009)17:2%3C103::AID-RSA2%3E3.0.CO;2-P"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_16_1","series-title":"Cambridge Series in Statistical and Probabilistic Mathematics","volume-title":"A user's guide to measure theoretic probability","author":"Pollard D."},{"key":"e_1_2_1_17_1","volume-title":"The Maple Handbook: Maple V Release 3","author":"Redfern D."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219098","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1219092.1219098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:42Z","timestamp":1750278162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1219092.1219098"],"URL":"https:\/\/doi.org\/10.1145\/1219092.1219098","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}