@inproceedings{2a6e0c6696574a91872efe2baba3730e,

title = "On the maximum satisfiability of random formulas",

abstract = "Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.",

keywords = "Benchmark testing, Computer science, Glass, H infinity control, Mathematics, NP-complete problem, Operations research, Physics, Stationary state, Statistics",

author = "D. Achlioptas and A. Naor and Y. Peres",

year = "2003",

doi = "10.1109/SFCS.2003.1238210",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "362--370",

booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",

note = "44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",

}