On the maximum satisfiability of random formulas

DOI10.1145/1219092.1219098zbMath1291.68175arXivmath/0305151OpenAlexW2131338348MaRDI QIDQ3546329

Assaf Naor, Yuval Peres, Demetrios Achlioptas

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0305151

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ Limits of discrete distributions and Gibbs measures on random graphs ⋮ Harnessing the Bethe free energy ⋮ The discrepancy of random rectangular matrices ⋮ On the Lower Bounds of Random Max 3 and 4-SAT ⋮ On the lower bounds of random Max 3 and 4-SAT

This page was built for publication: On the maximum satisfiability of random formulas