35 citations · 72 across the 5 of their papers we have counts for
Showing 2003Show all
2 papers · 1 filter
cond-mat.stat-mech2003★ 6 cited
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
Dimitris Achlioptas, Cristopher Moore
Many NP-complete constraint satisfaction problems appear to undergo a "phase transition'' from solubility to insolubility when the constraint density passes through a critical thre…
math.PR2003
On the Maximum Satisfiability of Random Formulas
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consi…