12 citations · 12 across the 3 of their papers we have counts for
6 papers
The rank of sparse random matrices
Amin Coja-Oghlan, Alperen A. Ergür, Pu Gao +2
We determine the rank of a random matrix over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the r…
Analysing Survey Propagation Guided Decimation on Random Formulas
Samuel Hetterich
Let be a uniformly distributed random -SAT formula with variables and clauses. For clauses/variables ratio the formula…
On universal hypergraphs
Samuel Hetterich, Olaf Parczyk, Yury Person
A hypergraph is called universal for a family of hypergraphs, if it contains every hypergraph as a copy. For the family of -uniform hypergr…
Local Algorithms for Graphs
David Gamarnik, Mathieu Hemery, Samuel Hetterich
We are going to analyze local algorithms over sparse random graphs. These algorithms are based on local information where local regards to a decision made by the exploration of a s…
The condensation phase transition in random graph coloring
Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich +2
Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remark…
On the chromatic number of random regular graphs
Amin Coja-Oghlan, Charilaos Efthymiou, Samuel Hetterich
Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if…