162 citations · 853 across the 40 of their papers we have counts for
3 papers · 2 filters
Lower bounds on the chromatic number of random graphs
Peter Ayre, Amin Coja-Oghlan, Catherine Greenhill
We prove that a formula predicted on the basis of non-rigorous physics arguments [Zdeborova and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic number of spa…
The rank of random matrices over finite fields
Amin Coja-Oghlan, Pu Gao
We determine the rank of a random matrix A over a finite field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rat…
The replica symmetric phase of random constraint satisfaction problems
Amin Coja-Oghlan, Tobias Kapetanopoulos, Noela Müller
Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark instances for algorithms and t…