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.
Further details will be added here in due course.
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.