24 citations · 27 across the 6 of their papers we have counts for
8 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 $…
Bad local minima exist in the stochastic block model
Amin Coja-Oghlan, Lena Krieg, Johannes Christian Lawnik +1
We study the disassortative stochastic block model with three communities, a well-studied model of graph partitioning and Bayesian inference for which detailed predictions based on…
The number of random 2-SAT solutions is asymptotically log-normal
Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller +4
We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that…
Noisy group testing via spatial coupling
Amin Coja-Oghlan, Max Hahn-Klimroth, Lukas Hintze +4
We study the problem of identifying a small set , , of infected individuals within a large population of size by testing groups of individuals simultaneously.…
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…