162 citations · 853 across the 40 of their papers we have counts for
Showing 2011 · math.COShow all
3 papers · 2 filters
math.CO2011★ 46 cited
The condensation transition in random hypergraph 2-coloring
Amin Coja-Oghlan, Lenka Zdeborova
For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence…
math.CO2011★ 11 cited
Analyzing Walksat on random formulas
Amin Coja-Oghlan, Alan Frieze
Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds…
math.CO2011★ 5 cited
The decimation process in random k-SAT
Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon
Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called Beli…