SCIENCE CHINA Information Sciences, Volume 59 , Issue 9 : 092101(2016) https://doi.org/10.1007/s11432-016-5526-8

A novel weighting scheme for random $k$-SAT

More info
  • ReceivedSep 28, 2015
  • AcceptedNov 3, 2015
  • PublishedAug 23, 2016



National Natural Science Foundation of China(11371225)

Fund of the State Key Lab of Software Development Environment(SKLSDE-2015ZX-05)



This work was supported by National Natural Science Foundation of China (Grant No. 11371225) and Fund of the State Key Lab of Software Development Environment (Grant No. SKLSDE-2015ZX-05).


[1] Achlioptas D, Peres Y. The threshold for random k-SAT is $2^{k}\log 2-O(k)$. J Amer Math Soc, 2004, 17947-973 CrossRef Google Scholar

[2] Frieze A, Wormald N C. Random k-SAT: a tight threshold for moderately growing $k$. Combinatorica, 2005, 25297-305 CrossRef Google Scholar

[3] Liu J, Gao Z S, Xu K. A Note on Random k-SAT for Moderately Growing k. Electron J Combin, 2012, 1924-305 Google Scholar

[4] Achlioptas D, Moore C. Ramdom $k$-SAT: two moments suffice to cross a sharp threshold. SIAM J Comput, 2006, 36740-762 CrossRef Google Scholar

[5] Achlioptas D, Moore C. The asymptotic order of the random k-SAT threshold. In: Proceeding of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, 2002. 126--127. Google Scholar

[6] Chvátal V, Reed B. Mick gets some (the odds are on his side). In: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 1992. 620--627. Google Scholar

[7] Erd\H{o}s P, Lovász L. Problems and results on 3-chromatic hypergraphs and some related questions. Colloq Math Soc J' a nos Bolyai, 1973, 10609-627 Google Scholar

[8] Friedgut E. Necessary and sufficient conditions for sharp thresholds of graph properties, and the $k$-SAT problem. J Amer Math Soc, 1999, 121017-1054 CrossRef Google Scholar

[9] Janson S, Stamatiou Y C, Vamvakari M. Bounding the unsatisfiability threshold of random 3-SAT. Random Struct Algor, 2000, 17103-116 CrossRef Google Scholar

[10] Ding J, Sly A, Sun N. Proof of the satisfiability conjecture for large $k$. arXiv:1411.0650. Google Scholar

[11] Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Algor, 2006, 28444-480 CrossRef Google Scholar

[12] Vorobyev F Y. A lower bound for the 4-satisfiability threshold. Discrete Math Appl, 2007, 17287-294 Google Scholar

[13] de Bruijn N G. Asymptotic Methods in Analysis. 3rd ed. New York: Dover Publications Inc, 1981. Google Scholar


Contact and support