Amin Coja-Oghlan

activity

20162026

most citedWalksat stalls well below the satisfiability threshold

24 citations · 27 across the 6 of their papers we have counts for

collaborators

Showing 2025Show all

2 papers · 1 filter

cs.DM2025

The random $k$ -SAT Gibbs uniqueness threshold revisited

Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill +4

We prove that for any $k \geq 3$ for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of rand…

math.CO2025

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 $k$ -XORSAT problem. Specifically, we derive an expli…

The random k-SAT Gibbs uniqueness threshold revisited

Belief Propagation Guided Decimation on Random k-XORSAT

The random $k$ -SAT Gibbs uniqueness threshold revisited