4 papers
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…
The random -SAT Gibbs uniqueness threshold revisited
Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill +4
We prove that for any for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of rand…
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 $…