Seminars
We regularly host seminars covering topics across our research areas.
Upcoming seminars
Time and Location  Speaker and Title 

May 21st, 2019 
Some recent advances in dynamic graph algorithms Many realworld 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 
Hierarchical clustering: Objective functions and new algorithms 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 bottomup (agglomerative) or topdown (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 randomgraph 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 CohenAddad, Claire Mathieu and Frederik MallmannTrenn. 
February 15th, 2019 
Geometric Semantic Genetic Programming 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 
Encoding Data Structures 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 preprocessing 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 
Testing logically defined properties on graphs of bounded degree 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 secondorder logic is testable with a constant number of queries in polylogarithmic running time on graphs of bounded treewidth. 
November 15th, 2018 
Algorithms for Out and InBranchings in Digraphs We will overview (mainly parameterized) algorithms for out and inbranchings in digraphs with extremal number of leaves. In particular, we will discuss an O^{*}(3.86^{k})time and polynomial space deterministic algorithm for deciding whether a digraph has an outbranching with at least k internal vertices (G., Reidl, Wahlstrom and Zehavi, JCSS 95, 2018) and solutions to two open problems by BangJensen et al. (2008, 2016) on kdistinct out and inbranchings (G., Reidl and Wahlstrom, JCSS 95, 2018).

November 19th, 2018 
Colouring Diamondfree Graphs The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) kcolouring. 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 cliquewidth is bounded for (diamond,P_{1}+2P_{2})free graphs. Our technique for handling this case is to reduce the graph under consideration to a kpartite graph that has a very specific decomposition. As a byproduct of this general technique we are also able to prove boundedness of cliquewidth for four other new classes of (H_{1},H_{2})free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of cliquewidth of (H_{1},H_{2})free graphs, and our five new classes of bounded cliquewidth reduce the number of open cases from 10 to 5.

October 29th, 2018 
Finding Small Cuts in Dense Graphs 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). 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 
Recent Advances on the Parameterized Complexity of Integer Linear Programming Integer Linear Programming (ILP) is probably the archetypical NPcomplete 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 polynomialtime if the constraint matrix is totally unimodular (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 nonzero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. wellknown decompositional parameters such as treedepth, treewidth, and cliquewidth, we will show that the well known blockstructured ILPs (e.g., nfold, twostage stochastic, 4block Nfold, and treefold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph. 
October 8th, 2018 
Graph Property Testing and Random Order Streams 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 constantquery testable in the adjacency list model can be tested with constant space in a singlepass 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 
Sunflowers and Quasisunflowers from Randomness Extractors 
July 9th, 2018 
Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems 
June 28th, 2018 
Spectral Sparsification and its Applications 
May 23rd, 2018 
Exact and Hybrid Approaches for Packing While Traveling and the Traveling Thief Problem 
October 30th, 2017 
Evolutionary Image Composition Using Feature Covariance Matrices 
September 7th, 2017 
An Investigation of Diversity in Searchbased Unit Test Suite Generation 
July 24th, 2017 
Improved runtime bounds for the Univariate Marginal Distribution Algorithm via anticoncentration 
June 13th, 2017 
Evaluating the performance of evolutionary algorithms for combinatorial optimisation 
June 13th, 2017 
Reimagining kary Trees in Haskell. Towards a Generic Dynamic Data Structure for Functional Programming Overcoming Non Distributivity: A Case Study through Functional Programming 
April 25th, 2017 
Runtime Analysis of Genetic Programming 
January 9th, 2017 
A Rigorous Proof that Standard Steady State GAs can Hillclimb Faster than Mutationonly EAs 
January 10th, 2017 
An Application of Stochastic Differential Equations to Evolutionary Algorithms 
January 11th, 2017 
Analysis of the Clearing DiversityPreserving Mechanism 