@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",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",
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",
}