6 papers
On sampling diluted Spin-Glasses with unbounded interactions
Charilaos Efthymiou, Kostas Zampetakis
Spin-glasses are natural Gibbs distributions that have been studied in Theoretical CS for many decades. Recently, they have been gaining attention from the community as they emerge…
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…
On sampling diluted Spin Glasses using Glauber dynamics
Charilaos Efthymiou, Kostas Zampetakis
Spin-glasses are Gibbs distributions that have been studied in CS for many decades. Recently, they have gained renewed attention as they emerge naturally in learning, inference, op…
Broadcasting with Random Matrices
Charilaos Efthymiou, Kostas Zampetakis
Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem for the related distributions on the tree, and on the sparse random graph $G(n,d/n…
The Lovász Local Lemma is Not About Probability
Dimitris Achlioptas, Kostas Zampetakis
Given a collection of independent events each of which has strictly positive probability, the probability that all of them occur is also strictly positive. The Lovász local lemma (…