{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T22:05:04Z","timestamp":1748469904848},"reference-count":20,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238210","type":"proceedings-article","created":{"date-parts":[[2004,3,2]],"date-time":"2004-03-02T02:26:50Z","timestamp":1078194410000},"page":"362-370","source":"Crossref","is-referenced-by-count":3,"title":["On the maximum satisfiability of random formulas"],"prefix":"10.1109","author":[{"given":"D.","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Peres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"19","first-page":"290","article-title":"Domain-independent extensions to GSAT: Solving large structured satisfiability problems","author":"selman","year":"0","journal-title":"Proc 13th International Joint Conference on Artificial Intelligence 1993"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811555"},{"journal-title":"The Maple Handbook Maple V Release 3 Third Ed","year":"1994","author":"redfern","key":"18"},{"article-title":"Computers and intractability","year":"1979","author":"garey","key":"15"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006314320276"},{"article-title":"9\/8-approximation algorithm for random max-3sat","year":"2002","author":"de la vega","key":"13"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988390"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0867"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780577"},{"key":"20","first-page":"440","article-title":"A new method for solving hard satisfiability problems","author":"selman","year":"0","journal-title":"Proc 10th National Conference on Artificial Intelligence 1992"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238210"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548486"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369156"},{"key":"5","first-page":"322","article-title":"On the satisfiability and maximum satisfiability of random 3-CNF formulas","author":"broder","year":"0","journal-title":"4th Annual Symposium on Discrete Algorithms 1993"},{"article-title":"The probabilistic method","year":"1991","author":"alon","key":"4"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"8","first-page":"364","article-title":"Random MAX 2-SAT and MAX CUT","author":"coppersmith","year":"0","journal-title":"14th Annual Symposium on Discrete Algorithms 2003"}],"event":{"name":"44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003","acronym":"SFCS-03","location":"Cambridge, MA, USA"},"container-title":["44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8767\/27770\/01238210.pdf?arnumber=1238210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T17:09:20Z","timestamp":1489424960000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238210\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":20,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238210","relation":{},"subject":[]}}