Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Coja-Oghlan, Amin; Frieze, Alan (2011)
Languages: English
Types: Preprint
Subjects: Mathematics - Combinatorics, Computer Science - Discrete Mathematics, 68R01
Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds a satisfying assignment of F in polynomial time w.h.p. if m/n<\rho 2^k/k for a certain constant \rho>0. This is an improvement by a factor of $\Theta(k)$ over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [2] D. Achlioptas, C. Moore: Random k-SAT: two moments suffice to cross a sharp threshold. SIAM Journal on Computing 36 (2006) 740-762.
    • [3] D. Achlioptas, Y. Peres: The threshold for random k-SAT is 2k ln 2 − O(k). Journal of the AMS 17 (2004) 947-973.
    • [4] M. Alekhnovich and E. Ben-Sasson: Linear upper bounds for random walk on small density random 3-CNFs. SIAM J. Comput. 36 (2007) 1248-1263.
    • [5] A. Broder, A. Frieze, E. Upfal: On the satisfiability and maximum satisfiability of random 3-CNF formulas. Proc. 4th SODA (1993) 322-330.
    • [6] M.-T. Chao, J. Franco: Probabilistic analysis of a generalization of the unit-clause literal selection heuristic for the k-satisfiability problem. Inform. Sci. 51 (1990) 289-314.
    • [7] V. Chva´tal, B. Reed: Mick gets some (the odds are on his side). Proc. 33th FOCS (1992) 620-627.
    • [8] A. Coja-Oghlan: A better algorithm for random k-SAT. SIAM J. Computing 39 (2010) 2823-2864.
    • [9] A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, D. Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. Proc. 20th SODA (2009) 451-460.
    • [10] A. Frieze, S. Suen: Analysis of two simple heuristics on a random instance of k-SAT. Journal of Algorithms 20 (1996) 312-355.
    • [11] M. Hajiaghayi, G. Sorkin: The satisfiability threshold of random 3-SAT is at least 3.52. IBM Research Report RC22942 (2003).
    • [12] S. Janson, T. Łuczak, A. Rucin´ ski: Random Graphs, Wiley 2000.
    • [13] A. Kaporis, L. Kirousis, E. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures and Algorithms 28 (2006) 444-480.
    • [14] D. Mitchell, B. Selman, H. Levesque: Hard and easy distribution of SAT problems. Proc. 10th AAAI (1992) 459-465.
    • [15] M. Molloy: Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27 (2005) 124-135.
    • [16] C. H. Papadimitriou: On selecting a satisfying truth assignment. Proc. 32nd FOCS (1991) 163-169.
    • [17] U. Scho¨ ning: A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proc. 40th FOCS (1999) 410-414.
    • [18] B. Selman, H. Kautz, B. Cohen: Local search strategies for satisfiability testing. In David S. Johnson, Michael A. Trick (eds.): Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26 (1996).
    • [19] G. Semerjian, R. Monasson: A study of pure random walk on random satisfiability problems with “physical” methods. Proc. 6th SAT (2003) 120-134.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Collected from