@inproceedings{97d5b9b64e6549ad993ba69cbd7c3df2,
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",
address = "United States",
}