A workshop on algorithms and complexity theory at the University of Oxford.
Leslie Goldberg is turning 60 this year!
We are celebrating her birthday with a day of talks on 20th June.
The talks will take place in the Bill Roscoe Lecture Theatre, Department of Computer Science.
If you want to participate, please contact the organisers.
Josep Diaz (UPC) A personal view of evolutionary dynamics
A focused survey about the research in Evolutionary Dynamics, during the decade 2010-2020.
Benjamin Doerr (Ecole Polytechnique) Mathematical analyses of multi-objective evolutionary algorithms
Evolutionary algorithms are state-of-the-art optimization
methods in a wide range of applications. Theoretical works have always
accompanied their design and analysis; however, due to the complex
structure of the probability spaces describing their runs, only very
simple algorithms could be analyzed rigorously. This has changed with
the first mathematical runtime analysis of the NSGA-II, the most
prominent multi-objective evolutionary algorithm (cited more than 60,000
times), followed soon after by the first analyses of other famous
multi-objective algorithms such as the NSGA-III, SMS-EMOA, SPEA2, and
PAES. In this talk, I will give a brief introduction to this area of
research, describe one surprising result, and state at least one problem
we cannot solve currently.
Martin Farach-Colton (NYU) How quickly does spam mix?
Spectral methods of page ranking in internet search engines represented a huge step forward and was the basis of Google’s early success. Still, page ranking became an arms race between spammers, who tried to modify the web graph to improve their rankings, and rankers, who tried to base their ranking of the unspammed web. We set up a two party game and discover who has the upper hand is this conflict.
Andreas Göbel (HPI) The Weisfeiler-Leman dimension of conjunctive queries
The 𝑘-Weisfeiler-Leman (WL) algorithm is an iterative process that initially assigns to each 𝑘-tuple of vertices 𝑣 of an input graph 𝐺 a colour depending on the isomorphism type of 𝑣 in 𝐺. In each step, the colour of every 𝑘-tuple is updated simultaneously, to take into account the colours of all “adjacent” tuples in 𝐺. This process terminates when the partition of 𝑘-tuples induced by the colours does not change after an update step, yielding a stable colouring. Given a function 𝑓 on graphs with the property that, for any pair of isomorphic graphs 𝐺 and 𝐺', 𝑓(𝐺) = 𝑓(𝐺'), its WL-dimension is the minimum 𝑘 such that, if 𝐺 and 𝐺' are indistinguishable by the 𝑘-dimensional WL-algorithm then 𝑓(𝐺) = 𝑓(𝐺'). A series of recent work connects the WL-dimension to other well-studied notions such as graph motifs, homomorphism counts and the expressiveness of Graph Neural Networks. In this talk I will go over my research ventures with Leslie and our co-authors in this area, presenting past and recent results.
Heng Guo (University of Edinburgh) A journey in approximate counting: from complex to quantum
In this talk I will review some of my collaborations with Leslie, including the "first" one, which is about complex weighted Ising models, and the most recent one, which is about simulating Gaussian boson sampling in graphs.
Mark Jerrum (QMUL) Graph 51
I will present an overview of the complexity of approximate counting, using the problem of counting graph homomorphisms as a sandbox, and Leslie's back catalogue as a guide. The graph that gives the talk its title will provide motivation.
Steven Kelk (Maastricht University) Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. In practice it is not uncommon to obtain two topologically distinct trees for the same set of species, and this motivates the use of distance measures to quantify dissimilarity. A well-known measure is the maximum agreement forest (MAF). Computing such a MAF is NP-hard and so considerable effort has been invested in finding FPT algorithms, parameterised by k, the number of components of a MAF. In this work we present improved algorithms for both the unrooted and rooted cases, with runtimes O*(2.846^k) and O*(2.3391^k) respectively. The key to our improvement is a novel branching strategy in which we show that any overlapping components obtained on the way to a MAF can be ‘split’ by a branching rule with favourable branching factor, and then the problem can be decomposed into disjoint subproblems to be solved separately.
This is joint work with David Mestel, Steven Chaplick and Ruben Meuwese.
John Lapinskas (University of Bristol) The instability of all backoff protocols
Backoff protocols live in a probabilistic model with simple rules that hide a deep and interesting question. Users arrive at a server at Poisson rate lambda > 0, in discrete time. Each user has a message they want to get through. If two or more users try to get their message through on the same time step, they all fail; if only one user tries, they succeed and leave the system. All users follow a backoff strategy - at every time step, they toss a biased coin. If they have so far tried and failed to get their message through i times, then they try again with probability p_i. In the real world, often p_i = 1/2^i - this is "binary exponential backoff" as featured in e.g. the design of Ethernet and the documentation of most major cloud services. Binary exponential backoff actually fails, in the sense that for *any* value of lambda (no matter how small) the expected return time to an empty state is infinite. The deep and interesting question is: is there any protocol p_1, p_2, ... for which the expected return time is finite? Aldous conjectured in 1987 that the answer is "no", again for any value of lambda. Here we prove that conjecture.
Marc Roth (QMUL) Parameterised counting complexity theory
In this talk, I will provide an introduction to parameterised counting and present a selection of the most influential results and techniques that have been introduced over the last decade. Moreover, I will discuss a couple of open problems that are either fundamental for our structural understanding of parameterised counting or that have prominently been studied in recent years but evaded a resolution so far. Specifically, in view of some of my past projects with Leslie, I will focus on challenges arising in the context of the combination of parameterised and approximate counting.