35 citations · 72 across the 5 of their papers we have counts for
5 papers
Hiding Satisfying Assignments: Two are Better than One
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-…
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe +1
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtainin…
The Chromatic Number of Random Regular Graphs
Dimitris Achlioptas, Cristopher Moore
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k…
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…
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…