research
∙
09/09/2023
Two-State Spin Systems with Negative Interactions
We study the approximability of computing the partition functions of two...
share
research
∙
05/22/2023
Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
We consider the performance of Glauber dynamics for the random cluster m...
research
∙
03/14/2023
Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process
The multi-type Moran process is an evolutionary process on a connected g...
research
∙
01/04/2023
Parameterised and Fine-grained Subgraph Counting, modulo 2
Given a class of graphs ℋ, the problem ⊕𝖲𝗎𝖻(ℋ) is defined as follows. Th...
research
∙
09/07/2022
Counting Subgraphs in Somewhere Dense Graphs
We study the problems of counting copies and induced copies of a small p...
research
∙
06/30/2022
Fast sampling of satisfying assignments from random k-SAT
We give the first nearly linear time algorithm to approximately sample s...
research
∙
03/31/2022
Instability of backoff protocols with arbitrary arrival rates
In contention resolution, multiple processors are trying to coordinate t...
research
∙
02/11/2022
Metastability of the Potts ferromagnet on random regular graphs
We study the performance of Markov chains for the q-state ferromagnetic ...
research
∙
11/07/2021
Fast sampling via spectral independence beyond bounded-degree graphs
Spectral independence is a recently-developed framework for obtaining sh...
research
∙
05/02/2021
Fast mixing via polymers for random graphs with unbounded degree
The polymer model framework is a classical tool from statistical mechani...
research
∙
05/01/2021
The complexity of approximating the complex-valued Ising model on bounded degree graphs
We study the complexity of approximating the partition function Z_Ising(...
research
∙
03/23/2021
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a smal...
research
∙
06/30/2020
Counting Homomorphisms to K_4-minor-free Graphs, modulo 2
We study the problem of computing the parity of the number of homomorphi...
research
∙
05/11/2020
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
Counting the independent sets of a graph is a classical #P-complete prob...
research
∙
05/03/2020
The complexity of approximating the complex-valued Potts model
We study the complexity of approximating the partition function of the q...
research
∙
04/28/2020
Fast algorithms for general spin systems on bipartite expanders
A spin system is a framework in which the vertices of a graph are assign...
research
∙
11/16/2019
Counting solutions to random CNF formulas
We give the first efficient algorithm to approximately count the number ...
research
∙
07/04/2019
The Complexity of Approximately Counting Retractions to Square-Free Graphs
A retraction is a homomorphism from a graph G to an induced subgraph H o...
research
∙
01/20/2019
Markov chains for the hard-core model via polymer models
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling alg...
research
∙
01/20/2019
A note on the high-fugacity hard-core model on bounded-degree bipartite expander graphs
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling alg...
research
∙
11/02/2018
Holant clones and the approximability of conservative holant problems
We construct a theory of holant clones to capture the notion of expressi...
research
∙
10/13/2018
Approximating Pairwise Correlations in the Ising Model
In the Ising model, we consider the problem of estimating the covariance...
research
∙
07/13/2018
The complexity of approximating the matching polynomial in the complex plane
We study the problem of approximating the value of the matching polynomi...
research
∙
07/02/2018
The Complexity of Approximately Counting Retractions
Let G be a graph that contains an induced subgraph H. A retraction from ...
research
∙
04/22/2018
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
We consider the problem of sampling from the Potts model on random regul...
research
∙
04/13/2018
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
We analyse the complexity of approximate counting constraint satisfactio...
research
∙
04/10/2018
Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree
The antiferromagnetic q-state Potts model is perhaps the most canonical ...
research
∙
04/06/2018
Phase Transitions of the Moran Process and Algorithmic Consequences
The Moran process is a randomised algorithm that models the spread of ge...
research
∙
11/01/2017