41 citations · 175 across the 19 of their papers we have counts for
7 papers · 1 filter
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for…
Algorithms for the ferromagnetic Potts model on expanders
Charlie Carlson, Ewan Davies, Nicolas Fraiman +3
We give algorithms for approximating the partition function of the ferromagnetic -color Potts model on graphs of maximum degree . Our primary contribution is a fully polynomi…
Computational thresholds for the fixed-magnetization Ising model
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
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 co…
Approximately counting independent sets of a given size in bounded-degree graphs
Ewan Davies, Will Perkins
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density…
An algorithmic framework for colouring locally sparse graphs
Ewan Davies, Ross J. Kang, François Pirot +1
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fix…
Efficient algorithms for the Potts model on small-set expanders
Charles Carlson, Ewan Davies, Alexandra Kolla
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of re…
Statistical physics approaches to Unique Games
Matthew Coulson, Ewan Davies, Alexandra Kolla +2
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Game…