Seminars

We regularly host seminars covering topics across our research areas.

Upcoming seminars

Time and Location Speaker and Title

May 21st, 2019
14:00-15:00
In COM-108 - Ada Lovelace Room.

Some recent advances in dynamic graph algorithms
Presented by Sayan Bhattacharya (University of Warwick).

Many real-world networks such as the ones arising out of Facebook and Twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge insertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of some recent developments in dynamic graph algorithms, focussing primarily on dynamic algorithms for graph coloring and maximum matching.

Past seminars

Time and Location Speaker and Title

February 25th, 2019
13:00-14:00
In COM-G12-Blue.

Hierarchical clustering: Objective functions and new algorithms
Presented by Varun Kanade (University of Oxford)

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Hierarchical clustering has mostly been studied in procedural terms, i.e., a hierarchical cluster tree is obtained using certain bottom-up (agglomerative) or top-down (divisive) heuristics, rather than finding a hierarchical cluster tree as the solution obtained by optimizing some suitable objective. Dasgupta (2016) identified this as a reason why the theory of hierarchical clustering lagged behind that of flat clustering and proposed an objective function. In this talk, we will take an axiomatic approach to identifying suitable objective functions for hierarchical clustering. We will also describe a new random-graph model with a planted hierarchy. New and existing algorithms and their performance in theory and on some preliminary experiments will be discussed.

Based on joint work with Vincent Cohen-Addad, Claire Mathieu and Frederik Mallmann-Trenn.

February 15th, 2019
14:00-15:00
In COM-G22-Blue.

Geometric Semantic Genetic Programming
Presented by Alberto Moraglio (University of Execeter)

Genetic Programming (GP) is the use of evolutionary algorithms to evolve computer programs and functions. Traditional GP searches the space of programs by using search operators that manipulate their syntactic representation (e.g., parse trees), regardless of their semantics (meaning). Semantic genetic programming is a rapidly growing trend that makes explicit use of information on program behaviour in the search to improve traditional GP performance. In this talk, I will give a broad introduction to Geometric Semantic Genetic Programming (GSGP) which uses genetic operators that search directly the semantic space of programs by exploiting geometric properties of this space. GSGP has the important property of inducing a unimodal error surface for any supervised learning problem in which fitness is calculated using a distance between outputs and targets on training data (like for instance in regression and classification). This property makes GSGP orders of magnitude faster than traditional GP, and it allows to analyse the time complexity of GSGP in a easy manner. This makes GSGP one of the most exciting and promising advances in GP.

December 3rd, 2018
14:00-15:00
In COM-G25.

Encoding Data Structures
Presented by Rajeev Raman (University of Leicester)

Driven by the increasing need to analyze and search for complex patterns in very large data sets, the area of compressed and succinct data structures has grown rapidly in the last 10–15 years. Such data structures have very low memory requirements, allowing them to fit into the main memory of a computer, which in turn avoids expensive computation on hard disks.

This talk will focus on a topic that has become popular recently: encoding “the data structure” itself. Some data structuring problems involve supporting queries on data, but the queries that need to be supported do not allow the original data to be deduced from the queries. This presents opportunities to obtain space savings even when the data is incompressible, by pre-processing the data, extracting only the information needed to answer the queries, and then deleting the data. The minimum information needed to answer the queries is called the effective entropy of the problem: precisely determining the effective entropy can involve interesting combinatorics.

November 27th, 2018
15:00-16:00
In COM-G25.

Testing logically defined properties on graphs of bounded degree
Presented by Isolde Adler (University of Leeds)

Property testing (for a property P) asks for a given graph, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of large data sets.

We show that in the bounded degree model, every property definable in monadic second-order logic is testable with a constant number of queries in polylogarithmic running time on graphs of bounded tree-width.

November 15th, 2018
14:00-15:00
In the Ada Lovelace Room.

Algorithms for Out- and In-Branchings in Digraphs
Presented by Gregory Gutin (Royal Holloway).

We will overview (mainly parameterized) algorithms for out- and in-branchings in digraphs with extremal number of leaves. In particular, we will discuss an O*(3.86k)-time and polynomial space deterministic algorithm for deciding whether a digraph has an out-branching with at least k internal vertices (G., Reidl, Wahlstrom and Zehavi, JCSS 95, 2018) and solutions to two open problems by Bang-Jensen et al. (2008, 2016) on k-distinct out- and in-branchings (G., Reidl and Wahlstrom, JCSS 95, 2018).

November 19th, 2018
14:00-15:00
In the Ada Lovelace Room.

Colouring Diamond-free Graphs
Presented by Konrad Dabrowski (University of Durham)

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for (diamond,P1+2P2)-free graphs. Our technique for handling this case is to reduce the graph under consideration to a k-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of (H1,H2)-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of (H1,H2)-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 10 to 5.

October 29th, 2018
14:00-15:00
In the Ada Lovelace Room.

Finding Small Cuts in Dense Graphs
Presented by Thomas Sauerwald (Cambridge University)

We consider the problem of approximating cut problems in dense graphs in sublinear time. Specifically, we consider everywhere dense graphs where every vertex has degree Ω(n) (cf. Arora, Karger, and Karpinski, STOC'95).
For the sparsest cut a(G), we present an algorithm that distinguishes everywhere dense graphs with a(G) ≥ ε n from those with a(G) ≤ cε n in Õ(n/ε) time, where 0 < c < 1 is a constant. Hence, there is a constant factor approximation algorithm for a(G) that runs in Õ(n/a(G)) time. For the bisection width bw(G), we present an algorithm that distinguishes everywhere dense graphs with bw(G) ≥ ε n^2 from those with bw(G) ≤ cε n^2 in Õ(1/ε + min(n, 1/ε^2)) time. Therefore, there is a constant factor approximation algorithm for bw(G) that runs in Õ(n^2/bw(G) + min(n, n^2/bw(G)^2)) time. We also prove that these runtimes are optimal up to logarithmic factors.

Our analysis is based on the combinatorial result that every everywhere dense graph admits a partitioning into a constant number of everywhere dense expanders.

October 17th, 2018
15:00-16:00
In the Ada Lovelace Room.

Recent Advances on the Parameterized Complexity of Integer Linear Programming
Presented by Sebastian Ordyniak.

Integer Linear Programming (ILP) is probably the archetypical NP-complete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomial-time if the constraint matrix is totally uni-modular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.

The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a non-zero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width, we will show that the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.

October 8th, 2018
16:00-17:00
In the Ada Lovelace Room.

Graph Property Testing and Random Order Streams
Presented by Pan Peng.

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. We show that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. We also show some results for general graphs, in particular, we present an algorithm for connectivity testing in general graphs.

July 27th, 2018
15:00-16:00
In the Ada Lovelace Room.

Sunflowers and Quasi-sunflowers from Randomness Extractors
Presented by Jiapeng Zhang (UC San Diego).

July 9th, 2018
12:00-13:00
In COM-G25.

Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems
Presented by Phan Trung Hai Nguyen (University of Birmingham).

June 28th, 2018
11:00-12:00
In the Ada Lovelace Room.

Spectral Sparsification and its Applications
Presented by Dr. He Sun (University of Edinburgh).

May 23rd, 2018
11:00-12:00
In the Ada Lovelace Room.

Exact and Hybrid Approaches for Packing While Traveling and the Traveling Thief Problem
Presented by Prof. Frank Neumann (University of Adelaide).

October 30th, 2017
11:00-12:00
In COM-G12 (Blue).

Evolutionary Image Composition Using Feature Covariance Matrices
Presented by Aneta Neumann (The University of Adelaide).

September 7th, 2017
11:00-12:00
In the Ada Lovelace Room.

An Investigation of Diversity in Search-based Unit Test Suite Generation
Presented by Nasser Albunian.

July 24th, 2017
11:00-12:00
In the Ada Lovelace Room.

Improved runtime bounds for the Univariate Marginal Distribution Algorithm via anti-concentration
Presented by Phan Trung Hai Nguyen.

June 13th, 2017
13:00-14:00
In COM-G22

Evaluating the performance of evolutionary algorithms for combinatorial optimisation
Presented by George O’Brien, John Foster, Matthew Hughes, James Pyle, and James Williams.

June 13th, 2017
10:30-12:00
In COM-G22

Re-imagining k-ary Trees in Haskell. Towards a Generic Dynamic Data Structure for Functional Programming
Presented by Juan Carlos.


Overcoming Non Distributivity: A Case Study through Functional Programming
Presented by Juan Carlos.

April 25th, 2017
12:00-13:00
In Meeting Room 1 (3.15), Diamond

Runtime Analysis of Genetic Programming
Presented by Andrei Lissovoi.

January 9th, 2017
14:00-15:00
In COM-G25

A Rigorous Proof that Standard Steady State GAs can Hillclimb Faster than Mutation-only EAs
Presented by Dogan Corus.

January 10th, 2017
13:30-15:00
In COM-G22

An Application of Stochastic Differential Equations to Evolutionary Algorithms
Presented by Jorge Perez Heredia.

January 11th, 2017
11:30-13:00
In COM-G25

Analysis of the Clearing Diversity-Preserving Mechanism
Presented by Edgar Covantes Osuna.