{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T03:12:27Z","timestamp":1729653147220,"version":"3.28.0"},"reference-count":30,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238209","type":"proceedings-article","created":{"date-parts":[[2004,3,1]],"date-time":"2004-03-01T21:26:50Z","timestamp":1078176410000},"page":"352-361","source":"Crossref","is-referenced-by-count":1,"title":["Linear upper bounds for random walk on small density random 3-CNFs"],"prefix":"10.1109","author":[{"given":"M.","family":"Alekhnovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Ben-Sasson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187704"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"article-title":"Improved bounds for 3-SAT","year":"2003","author":"iwama","key":"15"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00046-1"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0016"},{"key":"14","article-title":"Probabilistic 3-SAT algorithm further improved","volume":"2285","author":"hofmeister","year":"2002","journal-title":"Proc 19th STACS LNCS"},{"key":"11","first-page":"126","article-title":"Typical random 3-SAT formulae and the satisfiability threshold","author":"dubois","year":"2000","journal-title":"Proc 11th SODA"},{"key":"12","first-page":"322","article-title":"On the satisfiability and maximum satisfiability of random 3-CNF formulas","author":"broder","year":"0","journal-title":"Proceedings of the fourth annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"21","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"kirpatrick","year":"1983","journal-title":"Science"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_51"},{"key":"22","article-title":"Analysis of random processes via and-or tree evaluation","author":"luby","year":"0","journal-title":"Proceedings of the ACM-SIAM Symposium n Discrete Algorithms 1998"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185365"},{"year":"0","author":"park","key":"25"},{"article-title":"3-SAT in RTIME(O(1.32793n)) - Improving randomized local search by initializing strings of 3-clauses","year":"2003","author":"rolf","key":"26"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814612"},{"year":"0","author":"selman","key":"28"},{"key":"29","article-title":"Local Search Strategies for Satisfiability Testing","author":"selman","year":"0","journal-title":"DIMACS Series in Discrete Mathematics"},{"key":"3","first-page":"590","article-title":"Optimal myopic algorithms for random 3-SAT","author":"achlioptas","year":"2000","journal-title":"IEEE Symposium on Foundations of Computer Science"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00159-1"},{"key":"10","first-page":"1","article-title":"A deterministic 2 - 2\/k+1 algorithm for k-SAT based on local search","volume":"223","author":"danstin","year":"1999","journal-title":"Theoretical Computer Science"},{"key":"1","first-page":"28","article-title":"Setting two variables at a time yields a new lower bound for random 3-SAT","author":"achlioptas","year":"2000","journal-title":"Proc 32nd STOC"},{"key":"30","first-page":"440","article-title":"A new method for solving hard satisfiability problems","author":"selman","year":"0","journal-title":"Proc of the Tenth Natl Conference on Artificial Intelligence (AAAI-92) San Jose CA 1992"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1137\/0215080"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1145\/509973.509975"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24605-3_12"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380820"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267789"}],"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\/01238209.pdf?arnumber=1238209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:05:25Z","timestamp":1497571525000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238209\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":30,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238209","relation":{},"subject":[]}}