Arrow Research search

Author name cluster

Ewan Davies

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

FOCS Conference 2022 Conference Paper

Algorithms for the ferromagnetic Potts model on expanders

  • Charlie Carlson
  • Ewan Davies
  • Nicolas Fraiman
  • Alexandra Kolla
  • Aditya Potukuchi
  • Corrine Yap

We give algorithms for approximating the partition function of the ferromagnetic Potts model on d-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger’s algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.

Details

STOC Conference 2022 Conference Paper

Computational thresholds for the fixed-magnetization Ising model

  • Charlie Carlson
  • Ewan Davies
  • Alexandra Kolla
  • Will Perkins 0001

The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of +1 and −1 spins). In particular, letting β c (Δ) denote the critical inverse temperature of the zero-field Ising model on the infinite Δ-regular tree, and η Δ,β,1 + denote the mean magnetization of the zero-field + measure on the infinite Δ-regular tree at inverse temperature β, we prove, for the class of graphs of maximum degree Δ: (i) for β β c (Δ), there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations η such that |η| >η Δ,β,1 + . (iii) For β > β c (Δ), there is no FPRAS for the fixed-magnetization Ising model for magnetizations η such that |η| <η Δ,β,1 + unless NP=RP.

Details
v2026.09.13