Revised schedule of the workshop

The weather conditions in the UK on Sunday December 10 resulted in significant travel delays including flight cancellations. Because of this, the schedule of the workshop had to be revised.

The workshop is now scheduled to start on Monday with a lunch at 12:30 in the undergraduate common room, which is located on the ground floor of the Zeeman building (Maths Building). The registration for the workshop will open in parallel with the lunch.

All talks will be in the room MS.02 in the Zeeman Building (Mathematics). The conference dinner on Monday takes place in the Courtyard Room in the Scarman House on the campus; lunches, coffee breaks and the Tuesday dinner take place in the undergraduate common room in the Zeeman Building.

	Monday	Tuesday	Wednesday
9:00		Reinhard Diestel	Nikhil Bansal
9:45		Benny Sudakov	Joël Ouaknine
10:30		Coffee break	Coffee break
11:00		Ken-ichi Kawarabayashi	Angelika Steger
11:45		Harald Räcke	Mikkel Thorup
12:30	Lunch	Lunch	Lunch
14:00		Nati Linial
14:30	Welcome remarks
14:45	Daniela Kühn	Julia Wolf
15:30	Coffee break	Coffee break
16:00	Richard Cole	short talks Matthias Englert Anita Liebenau Péter Pál Pach Rahul Savani
16:45	Bernard Ries
18:15	Workshop Dinner	Dinner

Nikhil Bansal (TU Eindhoven): An algorithmic version of Banaszczyk's discrepancy theorem

In the 90's Banaszczyk developed a very powerful method for discrepancy problems, that goes beyond the partial coloring method. His result was based on deep ideas from convex geometry and was non-constructive. In this talk, I will present an alternate proof of this result, which is based on elementary techniques and also gives an efficient algorithm. This leads to the first efficient algorithms for several previous results in discrepancy.

Based on joint work with Daniel Dadush, Shashwat Garg and Shachar Lovett.

Richard Cole (NYU): The analysis of asynchronous coordinate descent

Finding an approximate minimum of high-dimensional convex functions is both a fundamental problem and one of considerable practical interest in machine learning and elsewhere. A method of choice is (sequential) stochastic coordinate descent. Given the high dimensions that arise in practice, asynchronous parallel implementations have received a lot of attention.

We show how to analyze the standard implementation in which coordinates are partitioned among processors and each processor repeatedly selects a coordinate to update uniformly at random from among its assigned coordinates. This analysis has a possibly unexpected connection to the analysis of (sequential) cyclic coordinate descent, for which we provide the best currently-known bounds, and we provide evidence that these bounds may be tight. We also give the first analysis of an asynchronous accelerated coordinate descent. The main question we are answering is for how many processors does one achieve linear speedup compared to the sequential versions of these algorithms.

This talk is intended to be self-contained. Our goal is to indicate the challenges that these analyses face and how we approach them.

This is joint work with Yun Kuen Cheung, Yixin Tao, and Ojas Deshpande.

Reinhard Diestel (Hamburg): Clusters as tangles

Clusters in big data sets are fuzzy objects that are difficult to capture if one aims to say for every element of the set to exactly which clusters it does or does not belong. This talk will introduce an alternative way of capturing and analysing clusters, a way gleaned from tangles in graphs.

In their work on graph minors, Robertson and Seymour introduced tangles as an indirect way to describe clusters, or regions of high cohesion, in a graph: rather than specifying which vertices and edges belong to such a cluster, as one would if one were to name a highly connected subgraph or minor, a tangle simply orients every low-order separation of the graph to one of its two sides, the side where the cluster is thought to lie. These oriented separations can then, collectively, be thought of as an area of high cohesion - even though it makes not sense to ask for a given vertex or edge which of these regions it belongs to. Robertson and Seymour proved two major theorems about tangles: the tangle-tree theorem, which says that all the main tangles in a graph can be distinguished by a small nested set of searations, and the tangle duality theorem, which says that if a graph has no large tangle then its entire structure is tree-like.

It turns out that, in order to prove these two theorems, one no longer needs any knowledge of the underlying graph: they can be expressed and proved purely in terms of the graph's separations, viewed as a natural poset with an order-reversing involution corresponding to flipping their sides. We may therefore define `abstract separation systems' axiomatically, and have a tangle-tree and a duality theorem for every instance of such a separation system.

The aim of this talk will be to make this precise by defining abstract separation systems and their tangles, and then to outline some rather diverse examples where viewing clusters as tangles can make a difference. In some of these, such as image segmentation, the aim is to capture `obvious' clusters in a new way, hoping that these might improve on existing methods. Others can produce clusters that may have been unknown so far, such as typical political mindsets in a population of voters. Yet others might apply to structures in mathematics itself, such as topological manifolds, and interact with existing notions of high local connectivity there.

Matthias Englert (Warwick): Comparison-based buffer management in QoS switches

We will present an open problem arising in the online management of packet buffers in Quality of Service network switches. The problem is formally modeled as follows. In each time step, an arbitrary number of packets arrive at a single buffer and only one packet can be transmitted. Packets can be of different importance which is implemented by attributing each packet with a non-negative value. The goal is to maximize the total value of transmitted packets. Depending on the precise model, there are additional constraints on the handling of packets. The question is how well an optimal (offline) solution can be approximated by algorithms that only take the relative order of packets, but not their specific value into account.

Ken-ichi Kawarabayashi (NII, Tokyo): Approximation algorithms for topological graph theory

Topological graph theory has given rise to fundamental algorithms for computing several graph invariants. Some of the central problems in this area concern computation of crossing number, graph genus, and vertex/edge deletion number. Since all of these problems are in general NP-hard, one should look at approximation algorithms that run in (quasi)polynomial time.

We obtain an approximation algorithm for genus of general graphs. We also obtain poly-logarithmic approximations for minimum vertex deletion of general graphs, and for genus of bounded degree graphs. These are the first approximation algorithms with a poly-logarithmic guarantee for any topological property of this kind.

Based on joint works with Tasos Sidiropoulos.

Daniela Kühn (Birmingham): Decompositions of graphs and hypergraphs

The study of combinatorial decomposition and packing problems has a long and rich history. I will give a survey of recent results in this area, including the proof of the existence of designs and its generalization to F-designs, progress on the tree-packing conjecture as well as progress on packings of small or sparse graphs into host graphs of large minimum degree.

Anita Liebenau (Monash): On the Erdős-Hajnal conjecture for trees

A graph class G is said to have the Erdős-Hajnal property if there is an ε>0 such that every graph G∈G contains a clique or an independent set of size |V(G)|^ε. Erdős and Hajnal conjectured that for every graph H the class of graphs forbidding H as an induced subgraph has the Erdős-Hajnal property. This conjecture remains widely open and Gyarfás proposed the following weaker conjecture. For every graph H, the class of graphs forbidding both H and its complement has the Erdős-Hajnal property.

In a breakthrough, Bousquet, Lagoutte, and Thomassé proved the weaker conjecture when H is a path. In fact, they proved that the class of graphs forbidding both a path and its complement has the strong Erdős-Hajnal property, which is known to imply the Erdős-Hajnal property. If G is the class of graphs forbidding both H and the complement of H, then this strong property can only be expected when H or its complement is acyclic. We prove that the class of graphs forbidding a tree T and its complement has the strong Erdős-Hajnal property as long as all vertices in T of degree larger than 2 lie on a common path, i.e. if T is a caterpillar with arbitrarily long legs.

Joint with Marcin Pilipczuk, Paul Seymour, and Sophie Spirkl.

Nati Linial (Hebrew University): High-dimensional permutations

In this talk I describe some of our results on high-dimensional permutations. We equate a permutation with a permutation matrix, i.e., an nxn array of 0/1 where every line (row or column) contains a single 1. Likewise a two-dimensional permutation is an nxnxn array of 0/1 where every line (row, column or shaft) contains exactly one 1. It is not hard to see that a two-dimensional permutation is synonymous with a Latin square. You should be able to figure out on your own what a d-dimensional permutation is. Here are some of our discoveries in this area and several problems that still remain open

- Enumeration problems - k-stochastic arrays and Birkhoff - von-Neumann theorem - Analogs of the Erdos-Szekeres theorem on monotone subsequences - Discrepancy problems - Generation and random generation of HD permutations

Based on joint papers with Zur Luria, Michael Simkin, and Maya Dotan.

Joël Ouaknine (Max-Planck-Institut for Software Systems, Saarbrücken): Decision problems for linear recurrence sequences

Linear recurrence sequences (LRS), such as the Fibonacci numbers, permeate vast areas of mathematics and computer science. In this talk, we consider three natural decision problems for LRS over the integers, namely the Skolem Problem (does a given LRS have a zero?), the Positivity Problem (are all terms of a given LRS positive?), and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). Such questions have applications in a wide array of scientific areas, ranging from theoretical biology and software verification to quantum computing and statistical physics. Perhaps surprisingly, the study of decision problems for linear recurrence sequences (and more generally linear dynamical systems) involves techniques from a variety of mathematical fields, including analytic and algebraic number theory, Diophantine geometry, and real algebraic geometry. I will survey some of the known results as well as recent advances and open problems.

This is joint work with James Worrell.

Péter Pál Pach (Warwick): Polynomials, rank and cap sets

In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z₄ⁿ and F_qⁿ are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets and mention some further applications of the method, for instance, the solution of the Erdős-Szemerédi sunflower conjecture, tight bound for Green’s arithmetic triangle removal lemma and growth rate of tri-colored sumfree sets.

Harald Räcke (TU München): Reordering buffer management in general metric spaces

In the reordering buffer management problem a sequence of requests arrive online in a finite metric space, and have to be processed by a single server. This server is equipped with a request buffer of size k and can decide at each point in time, which request from its buffer to serve next. Servicing of a request is simply done by moving the server to the location of the request. The goal is to process all requests while minimizing the total distance that the server is traveling inside the metric space.

This talk presents a deterministic algorithm for the reordering buffer management problem that achieves a competitive ratio of O(log Δ+min{log n,log k) in a finite metric space of n points and aspect ratio Δ. This is the first algorithm that works for general metric spaces and has just a logarithmic dependency on the relevant parameters. The guarantee is memory-robust, i.e., the competitive ratio decreases only slightly when the buffer-size of the optimum is increased to h=(1+ε)k. For memory robust guarantees our bounds are close to optimal.

Bernard Ries (Fribourg): On contact VPG graphs

In 2012, Asinowski et al. introduced the notion of vertex intersection graphs of paths in a grid (VPG graphs for short). Since then many research has been done on this graph class. In this talk we are interested in a subclass of this graph family, namely contact VPG graphs. The vertices in such a graph are represented by a family of interiorly disjoint paths in a rectangular grid and two vertices are adjacent if the corresponding paths touch. We give an overview of existing results as well as present some open problems related to this graph class.

Rahul Savani (Liverpool): Reachability switching games

We study the problem of deciding the winner of reachability switching games. These games provide deterministic analogues of Markovian systems. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. In the one- and two-player cases, the problem of determining the winner of a switching game turns out to be much harder than the problem of determining the winner of a Markovian game. We also study the structure of winning strategies in these games, and in particular we show that both players in a two-player reachability switching game require exponential memory.

Joint work with John Fearnley, Martin Gairing, and Matthias Mnich.

Angelika Steger (ETH Zürich): Resilience in random graph theory

Typical questions in random graph theory concern the question of whether a random graph satisfies a certain property. A more recent trend, introduced by Sudakov and Vu in 2008, is to study the resilience of such properties. For instance, local α-resilience implies that the property cannot be destroyed even if an adversary is allowed to remove an (arbitrary) α-fraction of all edges incident to each vertex. In this talk we report on recent developments in this field.

Benny Sudakov (ETH Zürich): Submodular minimization and set-systems with restricted intersections

Submodular function minimization is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which it remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial algorithms are known are parity constraints, i.e., optimizing submodular function only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose sub-determinants are bounded by two in absolute value.

We show that efficient submodular function minimization is possible even for a significantly larger class than parity constraints, i.e., over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. To obtain our results, we combine tools from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we establish an interesting connection between the correctness of a natural algorithm, and the non-existence of set systems with specific intersection properties.

Joint work with M. Nagele and R. Zenklusen

Mikkel Thorup (Copenhagen): Deterministic global minimum cut of a simple graph in near-linear time

We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts.

The previous fastest deterministic algorithm by Gabow from STOC'91 took ~O(m+k² n), where k is the edge connectivity, but k could be Omega(n).

At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes.

Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple input graph G with minimum degree d, producing a multigraph with ~O(m/d) edges which preserves all minimum cuts of G with at least 2 vertices on each side.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

This is a joint work with Ken-ichi Kawarabayashi.

Julia Wolf (Bristol): Some applications of relative entropy in additive combinatorics

In this talk we survey some recent applications of relative entropy in additive combinatorics. Specifically, we examine to what extent entropy-increment arguments can replace or even outperform more traditional energy-increment strategies or alternative approximation arguments based on the Hahn-Banach theorem, which have been instrumental in proving Szemerédi’s theorem and the Green-Tao theorem on long arithmetic progressions in the primes.