24 citations · 27 across the 6 of their papers we have counts for
4 papers · 1 filter
Fluctuations of the Ising free energy on Erdős-Rényi graphs
Amin Coja-Oghlan, Dominik Kaaser, Maurice Rolvien +2
We investigate the ferromagnetic Ising model on the Erdős-Rényi random graph with bounded average degree . Specifically, we determine the limiting distrib…
Belief Propagation Guided Decimation on Random k-XORSAT
Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang +3
We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random -XORSAT problem. Specifically, we derive an expli…
WalkSAT is linear on random 2-SAT
Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper +3
In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with variables in $…
Walksat stalls well below the satisfiability threshold
Amin Coja-Oghlan, Amir Haqshenas, Samuel Hetterich
Partly on the basis of heuristic arguments from physics it has been suggested that the performance of certain types of algorithms on random -SAT formulas is linked to phase tran…