24 citations · 27 across the 6 of their papers we have counts for
4 papers · 1 filter
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.…