research
∙
07/18/2023
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
We give a randomized algorithm that approximates the number of independe...
share
research
∙
04/05/2022
Algorithms for the ferromagnetic Potts model on expanders
We give algorithms for approximating the partition function of the ferro...
research
∙
11/04/2021
Computational thresholds for the fixed-magnetization Ising model
The ferromagnetic Ising model is a model of a magnetic material and a ce...
research
∙
10/11/2021
Packing list-colourings
List colouring is an influential and classic topic in graph theory. We i...
research
∙
02/09/2021
Approximately counting independent sets of a given size in bounded-degree graphs
We determine the computational complexity of approximately counting and ...
research
∙
04/15/2020
An algorithmic framework for colouring locally sparse graphs
We develop an algorithmic framework for graph colouring that reduces the...
research
∙
03/02/2020
Efficient algorithms for the Potts model on small-set expanders
We develop an approximation algorithm for the partition function of the ...
research
∙
11/04/2019
Statistical physics approaches to Unique Games
We show how two techniques from statistical physics can be adapted to so...
research
∙
12/28/2018
Occupancy fraction, fractional colouring, and triangle fraction
Given ε>0, there exists f_0 such that, if f_0 < f <Δ^2+1, then for any g...
research
∙
12/18/2018
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
For a graph G=(V,E), k∈N, and a complex number w the partition function ...
research
∙
12/04/2018