Leslie Ann Goldberg

Leslie Ann Goldberg

Auto-generated profile, based on publicly available information

Leslie Ann Goldberg

Department of Computer Science, University of Oxford, Oxford, UK

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 February 2017 in Journal of the ACM
Verified
Journal Article
Open access
PDF file
AGAndreas Galanis
Andreas Galanis
AGAndreas Göbel
Andreas Göbel
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JLJohn Lapinskas
John Lapinskas
DRDavid Richerby
David Richerby
The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation , in which all individuals are mutants, or extinction , in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n ). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an n -vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly n − 1/2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n ). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.

12 January 2016 in Random Structures & Algorithms
Verified
Journal Article
Open access
PDF file
JDJosep Díaz
Josep Díaz
LGLeslie Ann Goldberg
Leslie Ann Goldberg
DRDavid Richerby
David Richerby
MSMaria Serna
Maria Serna
The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is and . We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 137–159, 2016

29 March 2022 in Information and Computation
Verified
Journal Article
Open access
AGAndreas Galanis
Andreas Galanis
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JSJames Stewart
James Stewart
The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework. We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems.

1 January 2002 in Combinatorics, Probability and Computing
Verified
Journal Article
Open access
PDF file
LGLeslie Ann Goldberg
Leslie Ann Goldberg
MJMark Jerrum
Mark Jerrum
We consider the problem of sampling ‘unlabelled structures’, i.e., sampling combinatorial structures modulo a group of symmetries. The main tool which has been used for this sampling problem is Burnside’s lemma. In situations where a significant proportion of the structures have no nontrivial symmetries, it is already fairly well understood how to apply this tool. More generally, it is possible to obtain nearly uniform samples by simulating a Markov chain that we call the Burnside process: this is a random walk on a bipartite graph which essentially implements Burnside’s lemma. For this approach to be feasible, the Markov chain ought to be ‘rapidly mixing’, i.e., converge rapidly to equilibrium. The Burnside process was known to be rapidly mixing for some special groups, and it has even been implemented in some computational group theory algorithms. In this paper, we show that the Burnside process is not rapidly mixing in general. In particular, we construct an infinite family of permutation groups for which we show that the mixing time is exponential in the degree of the group.

3 February 2022 in computational complexity
Verified
Journal Article
Open access
PDF file
AGAndreas Galanis
Andreas Galanis
LGLeslie Ann Goldberg
Leslie Ann Goldberg
AHAndrés Herrera-Poyatos
Andrés Herrera-Poyatos
We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q \(\geq\) 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.

18 July 2019 in Algorithmica
Verified
Journal Article
Open access
PDF file
RCRadu Curticapean
Radu Curticapean
HDHolger Dell
Holger Dell
FFFedor Fomin
Fedor Fomin
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JLJohn Lapinskas
John Lapinskas
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class \(\mathsf {\#RH}\Pi _1\). It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in \(\mathsf {\#RH}\Pi _1\), and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms.