Term 1 
Mon 12 Oct 2015
13:00 in E245 
Simon
Griffiths (Oxford)
Crossing probabilities in Voronoi Percolation
Show
Abstract
Please see here for a PDF version.

Mon 19 Oct 2015
13:00 in E245 
Nicolai
Vorobjov (Bath)
Topological lower bounds for
computation trees and arithmetic networks
Show
Abstract
Please see here for a PDF version.

Mon 26 Oct 2015
13:00 in E245 
Dirk
Sudholdt (Sheffield)
On the Analysis of Evolutionary
Algorithms  How Crossover Speeds Up BuildingBlock
Assembly in Genetic Algorithms
Show
Abstract
Evolutionary algorithms are popular generalpurpose
algorithms for optimisation and design that use search
operators like mutation, crossover and selection to
"evolve" a population of good solutions. In the past
decades there has been a long and controversial debate
about when and why the crossover operator is useful. The
buildingblock hypothesis assumes that crossover is
particularly helpful if it can recombine good "building
blocks", i. e. short parts of the genome that lead to
high fitness. However, all attempts at proving this
rigorously have been inconclusive. As of today, there is
no rigorous and intuitive explanation for the usefulness
of crossover. In this talk we provide such an
explanation. For functions where "building blocks" need
to be assembled, we prove rigorously that many
evolutionary algorithms with crossover are twice as fast
as the fastest evolutionary algorithm using only
mutation. The reason is that crossover effectively turns
fitnessneutral mutations into improvements by combining
the right building blocks at a later stage. This also
leads to surprising conclusions about the optimal
mutation rate.

Mon 2 Nov 2015
13:00 in E245 
Michael
Rovatsos (Edinburgh)
Algorithms for the Sharing Economy
Show
Abstract
Recently, a new type of Webbased "sharing economy" applications have
emerged that aim at making use of untapped excess capacity in goods
and services through Webbased platforms for trading resources and
services. In this talk I will discuss various interesting problems
related to mechanism design and combinatorial optimisation that these
applications pose: dealing with unmanageable solution spaces,
humancentric interaction and negotiation models, and the design of
appropriate incentives to influence individual and collective
behaviour. I will give examples for some of these problems and
partial approaches to address them based on recent work we have done
on ridesharing, and point at potential directions for future work.

Mon 9 Nov 2015
13:00 in E245 
Kristina
Vuskovic (Leeds)
Title: Coloring squarefree Berge graphs
Show
Abstract
We consider the class of graphs that does not contain as induced subgraphs chordless cycles of odd length greater than 3, their complements and chordless cycles of length 4 (squarefree Berge graphs). We present a purelygraph theoretical algorithm that produces an optimal coloring for the graphs in this class. This is joint work with Chudnovsky, Lo, Maffray and Trotignon.
This is a subclass of perfect graphs, that have been extensively studied in the last 50 years. In 1981 Grötschel, Lovász and Schrijver showed that perfect graphs can be optimally colored in polynomial time. Their algorithm uses the ellipsoid method and is usually considered impractical. The last big open problem in the area is to find a purely combinatorial polynomial time coloring algorithm for perfect graphs.

Mon 16 Nov 2015
13:00 in E245 
Peter
Kling (SFU, Canada)
Plurality Consensus – Shuffle & Balance Your Opinions
Show
Abstract
Consider a huge network where each node holds one of k opinions. Plurality consensus asks for simple and fast distributed protocols to determine the most common opinion. A particularly important aspect of protocol simplicity is a small memory footprint. One reason for this is that plurality consensus nicely models certain biological and chemical processes involving the interaction between very small state machines (aka cells or molecules). Another is that plurality consensus can be used in huge networks of very cheap sensors to collect reliable data. We highlight an interesting relation between plurality consensus and load balancing, building upon recent results for the latter to provide clean and flexible protocols for the former. This allows us to improve the state of the art for a large range of problem parameters. In particular, we simplify and generalize a recent result by Alistarh et al (PODC'15) and, at the same time, improve the runtime by a logarithmic factor.

Mon 23 Nov 2015
13:00 in E245 
Daniel
Kral (Warwick)
Algorithms for FO model checking
Show
Abstract
Properties of relational structures that can be expressed
in the first order (FO) logic belong among the simplest ones.
Yet many algorithmic questions concerning them are challenging.
In this talk, we focus on deciding FO properties for graphs.
Such properties include e.g. the existence of a subgraph or
a dominating set of a fixed size. Every FO property can can
be decided in polynomial time. However, we aim at constructing
FPT algorithms, i.e., algorithms with the degree of the polynomial
in the running time estimate independent of an FO property.
Classical results on deciding FO properties include the almost
lineartime algorithm of Frick and Grohe for graphs with locally
bounded treewidth. We start with surveying more recent results
on other classes of sparse graphs, including those that have
bounded expansion or that are nowheredense. We then focus
on intersection graphs of intervals with finitely many lengths,
where the current techniques do not seem to readily apply, and
we design an FPT algorithm for deciding FO properties for this
class of graphs.
The talk contains results obtained during joint work
with Ganian, Hlineny, Obdrzalek, Schwartz and Teska.

Mon 30 Nov 2015
13:00 in E245 
Barny
Martin (Middlesex)
Minimal generating sets for direct powers of finite algebras
Show
Abstract
This talk will be mostly mathematical. Let A be a finitedomain algebra. We can associate a function f_A:N>N, giving the cardinality of the minimal generating sets of the sequence A, A^2, A^3, ... as f(1), f(2), f(3), ..., respectively. We may say A has the gGP if f(m) \leq g(m) for all m. The question then arises as to the growth rate of f and specifically regarding the behaviours constant, logarithmic, linear, polynomial and exponential. Wiegold proved that if A is a finite semigroup then f_A is either linear or exponential, with the former prevailing precisely when A is a monoid. This dichotomy classification may be seen as a gap theorem because no growth rates intermediate between linear and exponential may occur. We say A enjoys the polynomially generated powers property (PGP) if there exists a polynomial p so that f_A=O(p) and the exponentially generated powers property (EGP) if there exists a constant b so that f_A=Omega(g) where g(i)=b^i. A new result by Dmitriy Zhuk states that this gap between PGP and EGP holds for all finitedomain algebras. Furthermore, the PGP cases obey a certain property called switchability. This "switchability" was introduced in the context of the Quantified Constraint Satisfaction Problem (QCSP) as something more general than "collapsibility", also introduced in the context of the QCSP. We study the relationship between switchability and collapsibility where it seems there are still interesting things to be learnt.

Mon 7 Dec 2015
13:00 in E245 
Petra
Berenbrink (SFU, Canada)
Efficient Plurality Consensus on the Complete Graph
Show
Abstract
Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol to gain knowledge about opinions in their neighborhood, which might cause them to change their opinion. The goal is to find a protocol that, with high probability, causes all nodes to adopt the plurality (the opinion initially supported by the most nodes). A major open question has been whether there is a protocol for the complete graph that converges in polylogarithmic time and uses only polylogarithmic memory (per node). This paper answers this question affirmative.
We propose two plurality consensus protocols that require only an arbitrarily small constant multiplicative bias towards the plurality. Both assume a complete graph and realize communication via a random phone call model. The first protocol is very simple, and achieves plurality consensus within O(log k · log log n) rounds using log k + Θ(log log k) bits of memory. The second protocol achieves plurality consensus within O(log log n · log n) rounds using only log k + O(1) bits of memory. The latter result disproves a conjecture of Becchetti et al. (SODA 2015) implying that any protocol using log k + O(1) bits of memory has runtime at least linear in k in the worst case. At the heart of our protocols lies the usage of an undecided state, a technique introduced by Angluin et al.

Mon 14 Dec 2015
13:00 in E245 
Mark
Jerrum (Queen Mary)
A switch Markov chain for perfect matchings
Show
Abstract
Motivated by a sampling problem arising in statistics, Diaconis, Graham and Holmes
introduced a simple Markov chain, the switch chain, on the set of all perfect
matchings in a bipartite graph G. Two basic questions about this Markov chain are:
for which class of graphs is the switch chain ergodic, and for which is it rapidly
mixing? (I.e., does the switch chain have a limiting distribution and, if so,
what is its rate of convergence?) I'll present a precise answer to the ergodicity
question and close bounds on the mixing question. In particular, I'll give some
rough indications of a proof that the mixing time of the switch chain is polynomial
in the size of the graph G in the case that G is monotone (a.k.a. a bipartite
permutation graph). The class of monotone graphs includes examples of interest
in the statistical setting.
This is joint work with Martin Dyer and Haiko Müller (Leeds).

Term 2 
Mon 18 Jan 2016
13:00 in E245 
Alonso CastilloRamirez (Durham)
Finite semigroups of cellular automata
Show
Abstract
Since first introduced by John von Neumann, cellular automata (CA) have grown in importance in areas such as computer science, physics and theoretical biology. In its classical setting, a cellular automaton is a transformation of the set of all configurations of a regular grid such that the image of any particular cell of the grid only depends on the state of a finite number of its neighbours. The most famous example of this is Conway's Game of Life, whose setting is a discrete twodimensional infinite grid.
In this talk, we review some recent group theoretic results in the theory of CA, and we embark in the study of CA of finite configurations of finite grids from the point of view of semigroup theory. This is joint work with Maximilien Gadouleau.

Mon 25 Jan 2016
13:00 in E245 
Alexandre
Stauffer (Bath)
Rumor Spreading on Dynamic Graphs
Show
Abstract
We consider a classical randomized algorithm (known as pushpull) to distribute a rumor among the vertices of a graph. In this algorithm, at each step, each vertex contacts a uniformly random neighbor to either transmit the rumor or get to know the rumor.
We focus on the case where the graph changes while the rumor is being spread, and derive conditions on the dynamics that guarantee an upper bound on the spreading time.

Mon 1 Feb 2016
13:00 in E245 
Prudence
Wong (Liverpool)
Scheduling for Electricity Cost in Smart Grid
Show
Abstract
We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. In this talk we will consider different variants of this problem, presenting exact algorithms, approximation algorithms and online algorithms.

Mon 8 Feb 2016
13:00 in E245 
Andre Nichterlein (Durham)
Data reduction for Degree Constraint Completion Problems in Small Degree Graphs
Show
Abstract
We study provably effective and efficient data reduction for a class of
NPhard graph modification problems based on vertex degree properties.
Our main positive result is fixedparameter tractability for NPhard
graph completion (that is, edge insertion) cases while there is no hope
to achieve analogous results for the corresponding vertex or edge
deletion versions.
Our algorithms are based on a method that transforms graph completion
problems into efficiently solvable number problems and then translates
the results back into the graph setting.
Indeed, our core observation is that we encounter a winwin situation in
the sense that either the number of edge insertions is small (and thus
faster to find) or the problem is polynomialtime solvable.
This approach leads to a general method of approaching polynomialtime
preprocessing degree constraint completion problems on undirected as
well as directed graphs.
This talk is based on joint work with Robert Bredereck, Vincent Froese,
Sepp Hartung, Marcel Koseler, Marcelo Millany, Rolf Niedermeier, and
Ondra Suchy.

Mon 15 Feb 2016
13:00 in E245 
Andrei
Krokhin (Durham)
The complexity of generalvalued
CSPs
Show
Abstract
An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. The case when all functions take only values 0 and infinity corresponds to the standard CSP. We study (assuming that P ≠NP) how the complexity of VCSP depends on the set of functions allowed in the instances, the socalled constraint language. Massive progress has been made in the last three years on this complexity classification question, and our work gives, in a way, the final answer to it, modulo the complexity of CSPs.
This is joint work with Vladimir Kolmogorov and Michal Rolinek (both from IST Austria).

Mon 22 Feb 2016
13:00 in E245 
Rui Carvalho (Durham)
Critical behaviour in charging of electric vehicles
Show
Abstract
The increasing penetration of electric vehicles over the coming decades, taken together with the high cost to upgrade local distribution networks and consumer demand for home charging, suggest that managing congestion on low voltage networks will be a crucial component of the electric vehicle revolution and the move away from fossil fuels in transportation. Here, we model the maxflow and proportional fairness protocols for the control of congestion caused by a fleet of vehicles charging on two realworld distribution networks. We show that the system undergoes a continuous phase transition to a congested state as a function of the rate of vehicles plugging to the network to charge. We focus on the order parameter and its fluctuations close to the phase transition, and show that the critical point depends on the choice of congestion protocol. Finally, we analyse the inequality in the charging times as the vehicle arrival rate increases, and show that charging times are considerably more equitable in proportional fairness than in maxflow.

Mon 29 Feb 2016
13:00 in E245 
Felix Joos
(Birmingham)
How to determine if a random graph with a fixed degree sequence has a giant component
Show
Abstract
For a fixed degree sequence D=(d_1,...,d_n), let G(D) be a uniformly chosen (simple) graph on {1,...,n} where the vertex i has degree d_i. We determine whether G(D) has a giant component essentially imposing no conditions on D. We simply insist that the sum of the degrees in D which are not 2 is at least f(n) for some function f going to infinity with n.
This is joint work with Guillem Perarnau, Dieter Rautenbach and Bruce Reed.

Mon 7 March 2016
13:00 in E245 
Iain
Stewart (Durham)
Some mathematics of data centre
networks, part 1
Show
Abstract
I will explain the technological drivers as regards the design of modern data centre networks and show how this design process gives rise to interesting problems the solution of which involves various aspects of algorithms, combinatorics and graph theory such as isoperimetric sets, transversal designs and routing.

Mon 14 March 2016
13:00 in E245 
Hajo Broersma (Twente, NL)
Subgraph conditions for cyclic properties of graphs
Show
Abstract
Many results on cyclic properties of graphs involve restrictions on the graph in terms of certain fixed forbidden induced subgraphs. We will start with a survey of some now more or less classical results, and then concentrate on more recent results and open questions.

Term 3 
Mon 16 May 2016
13:00 in E245 
Iain
Stewart (Durham)
Some mathematics of data centre
networks, part 2
Show
Abstract
I will explain the technological drivers as regards the design of modern data centre networks and show how this design process gives rise to interesting problems the solution of which involves various aspects of algorithms, combinatorics and graph theory such as isoperimetric sets, transversal designs and routing.
