124 citations · 239 across the 28 of their papers we have counts for
3 papers · 1 filter
Approximating observables is as hard as counting
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph.…
Fast sampling of satisfying assignments from random -SAT with applications to connectivity
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +4
We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random -SAT model when the density of the formula scales exponentially with . The…
Metastability of the Potts ferromagnet on random regular graphs
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg +3
We study the performance of Markov chains for the -state ferromagnetic Potts model on random regular graphs. It is conjectured that their performance is dictated by metastabilit…