10 Year Anniversary DIMAP Workshop  Revised Schedule
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  Kenichi 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 nonconstructive. 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 highdimensional 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 currentlyknown 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 selfcontained. 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 loworder 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 tangletree 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 treelike.
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 orderreversing involution corresponding to flipping their sides. We may therefore define `abstract separation systems' axiomatically, and have a tangletree 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): Comparisonbased 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 nonnegative 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.
Kenichi 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 NPhard, 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 polylogarithmic approximations for minimum vertex deletion of general graphs, and for genus of bounded degree graphs. These are the first approximation algorithms with a polylogarithmic 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 Fdesigns, progress on the treepacking 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ősHajnal conjecture for trees
A graph class G is said to have the ErdősHajnal 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ősHajnal 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ősHajnal 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ősHajnal property, which is known to imply the ErdősHajnal 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ősHajnal 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): Highdimensional permutations
In this talk I describe some of our results on highdimensional 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 twodimensional 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 twodimensional permutation is synonymous with a Latin square. You should be able to figure out on your own what a ddimensional permutation is. Here are some of our discoveries in this area and several problems that still remain open
 Enumeration problems  kstochastic arrays and Birkhoff  vonNeumann theorem  Analogs of the ErdosSzekeres 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 (MaxPlanckInstitut 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 3term arithmetic progressions in groups like Z_{4}^{n} and F_{q}^{n} 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ősSzemerédi sunflower conjecture, tight bound for Green’s arithmetic triangle removal lemma and growth rate of tricolored 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 memoryrobust, i.e., the competitive ratio decreases only slightly when the buffersize 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 twoplayer variants of these games. We show that the zeroplayer case is NLhard, the oneplayer case is NPcomplete, and that the twoplayer case is PSPACEhard and in EXPTIME. In the one and twoplayer 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 twoplayer 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 setsystems 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 nontrivial 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 oddcut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants 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 nonexistence 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 nearlinear time
We present a deterministic nearlinear time algorithm that computes the edgeconnectivity 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 nearlinear 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^{2} 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 nearlinear 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 nearlinear time algorithm, we will decompose the problem via lowconductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for lowconductance 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 Kenichi 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 entropyincrement arguments can replace or even outperform more traditional energyincrement strategies or alternative approximation arguments based on the HahnBanach theorem, which have been instrumental in proving Szemerédi’s theorem and the GreenTao theorem on long arithmetic progressions in the primes.