124 citations · 239 across the 28 of their papers we have counts for
3 papers · 1 filter
Counting solutions to random CNF formulas
Andreas Galanis, Leslie Ann Goldberg, Heng Guo +1
We give the first efficient algorithm to approximately count the number of solutions in the random -SAT model when the density of the formula scales exponentially with . The…
Improved Strong Spatial Mixing for Colorings on Trees
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes +2
Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is…
Fast algorithms at low temperatures via Markov chains
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain…