Seminars1516

Please see here for a PDF version.

Please see here for a PDF version.

Evolutionary algorithms are popular general-purpose 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 building-block 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 fitness-neutral mutations into improvements by combining the right building blocks at a later stage. This also leads to surprising conclusions about the optimal mutation rate.

Recently, a new type of Web-based “sharing economy” applications have emerged that aim at making use of untapped excess capacity in goods and services through Web-based 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, human-centric 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.

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 (square-free Berge graphs). We present a purely-graph 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.

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.

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 linear-time algorithm of Frick and Grohe for graphs with locally bounded tree-width. We start with surveying more recent results on other classes of sparse graphs, including those that have bounded expansion or that are nowhere-dense. 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.

This talk will be mostly mathematical. Let A be a finite-domain 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 g-GP 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 finite-domain 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.

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.

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).

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 two-dimensional 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.

We consider a classical randomized algorithm (known as push-pull) 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.

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.

We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. Our main positive result is fixed-parameter tractability for NP-hard 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 win-win situation in the sense that either the number of edge insertions is small (and thus faster to find) or the problem is polynomial-time solvable. This approach leads to a general method of approaching polynomial-time 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.

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 so-called 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).

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 max-flow and proportional fairness protocols for the control of congestion caused by a fleet of vehicles charging on two real-world 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 max-flow.

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.

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.

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.

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.