Leslie Ann Goldberg

research

∙ 09/09/2023

Two-State Spin Systems with Negative Interactions

We study the approximability of computing the partition functions of two...

0 Yumou Fei, et al. ∙

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...

0 Andreas Galanis, et al. ∙

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...

0 Leslie Ann Goldberg, et al. ∙

research

∙ 01/04/2023

Parameterised and Fine-grained Subgraph Counting, modulo 2

Given a class of graphs ℋ, the problem ⊕𝖲𝗎𝖻(ℋ) is defined as follows. Th...

0 Leslie Ann Goldberg, et al. ∙

research

∙ 09/07/2022

Counting Subgraphs in Somewhere Dense Graphs

We study the problems of counting copies and induced copies of a small p...

0 Marco Bressan, et al. ∙

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...

0 Andreas Galanis, et al. ∙

research

∙ 03/31/2022

Instability of backoff protocols with arbitrary arrival rates

In contention resolution, multiple processors are trying to coordinate t...

0 Leslie Ann Goldberg, et al. ∙

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 ...

0 Amin Coja-Oghlan, et al. ∙

research

∙ 11/07/2021

Fast sampling via spectral independence beyond bounded-degree graphs

Spectral independence is a recently-developed framework for obtaining sh...

0 Ivona Bezakova, et al. ∙

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...

0 Andreas Galanis, et al. ∙

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(...

0 Andreas Galanis, et al. ∙

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...

0 Jacob Focke, et al. ∙

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...

0 Jacob Focke, et al. ∙

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...

0 Leslie Ann Goldberg, et al. ∙

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...

0 Andreas Galanis, et al. ∙

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...

0 Andreas Galanis, et al. ∙

research

∙ 11/16/2019

Counting solutions to random CNF formulas

We give the first efficient algorithm to approximately count the number ...

0 Andreas Galanis, et al. ∙

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...

0 Jacob Focke, et al. ∙

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...

0 Zongchen Chen, et al. ∙

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...

0 Andreas Galanis, et al. ∙

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...

0 Miriam Backens, et al. ∙

research

∙ 10/13/2018

Approximating Pairwise Correlations in the Ising Model

In the Ising model, we consider the problem of estimating the covariance...

0 Leslie Ann Goldberg, et al. ∙

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...

0 Ivona Bezakova, et al. ∙

research

∙ 07/02/2018

The Complexity of Approximately Counting Retractions

Let G be a graph that contains an induced subgraph H. A retraction from ...

0 Jacob Focke, et al. ∙

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...

0 Antonio Blanca, et al. ∙

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...

0 Miriam Backens, et al. ∙

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 ...

0 Andreas Galanis, et al. ∙

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...

0 Leslie Ann Goldberg, et al. ∙

research

∙ 11/01/2017

Inapproximability of the independent set polynomial in the complex plane

We study the complexity of approximating the independent set polynomial ...

0 Ivona Bezakova, et al. ∙

Leslie Ann Goldberg

Featured Co-authors