TBA

The crossing number problem for graphs is to draw (or embed) a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications. On the other hand, the problem is notoriously difficult. In 1973, Erdös and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved." For example, the crossing numbers of complete and complete bipartite graphs are still unknown in general. The case of the complete bipartite graph is known as Turán's brickyard problem, and was already posed by Paul Turán in the 1940's. Moreover, even for cubic graphs, it is NP-hard to compute the crossing number.

Different types of crossing numbers may be defined by restricting drawings; thus the k-page (book) crossing number corresponds to drawings where all vertices are drawn on a line (the spine of a book), and each edge on one of k planes intersecting the spine (the book pages). It is conjectured that the two-page and normal crossing numbers coincide for complete and complete bipartite graphs. In this talk, we will survey some recent results, where improved lower bounds were obtained for (k-page) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques. (Joint work with D.V. Pasechnik and G. Salazar)

If A is a large subset of {1,...,N}, then how long an arithmetic progression must A+A = {a+b : a,b in A} contain? Answers to this ostensibly combinatorial question were given by Bourgain and then Green, both using some very beautiful Fourier analytic techniques. Here I plan to discuss a new attack on the problem that rests on a lemma in discrete geometry, proven by a random sampling technique, and applied in a discrete analytic context. We shall not use any deep results, and we shall try to keep things as self-contained as possible.

Based on joint work with Ernie Croot and Izabella Laba.

Extremal Combinatorics is one of the central branches of discrete mathematics which deals with the problem of estimating the maximum possible size of a combinatorial structure which satisfies certain restrictions. Often, such problems have also applications to other areas including Theoretical Computer Science, Additive Number Theory and Information Theory. In this talk we will illustrate this fact by several closely related examples focusing on a recent work with Alon and Moitra.

We introduce the so-called Treewidth Reduction Theorem. Given a graph G, two specified vertices s and t, and an integer k, let C be the union of all minimal s-t (vertex) separators of size at most k. Furthermore, let G^* be the graph obtained from G by contracting all the connected components of G - C into single vertices. The theorem states that the treewidth of G^* is bounded by a function of k and that the graph G^* can be computed in linear time for any fixed k.

The above theorem allows us to solve the following generic graph separation problem in linear time for every fixed k. Let G be a graph with two specified vertices s and t and let Z be a hereditary class of graphs. The problem asks if G has an s-t vertex separator S of size at most k such that the subgraph induced by S belongs to the class Z.

In other words, we show that this generic problem is fixed-parameter tractable. This allows us to resolve a number of seemingly unrelated open questions scattered in the literature concerning fixed-parameter tractability of various graph separation problems under specific constraints.

The role of the Treewidth Reduction Theorem is that it reduces an arbitrary instance of the given problem to an instance of the problem where the treewidth is bounded. Then the standard methodology using Courcelle's theorem can be applied.

The purpose of this talk is to convey the main technical ideas of the above work at an intuitive level. The talk is self-contained. In particular, no prior knowledge of parameterized complexity, treewidth, and Courcelle's theorem is needed. Everything will be intuitively defined in the first 10-15 minutes of the talk.

Joint work with D. Marx and B. O'Sullivan. Available at http://arxiv.org/abs/1110.4765.

The framework of query complexity is a setting in which quantum computers are known to be significantly more powerful than classical computers. In this talk, I will discuss some new results in the model of exact quantum query complexity, where the goal is to compute a boolean function f with certainty using the smallest possible number of queries to the input. It is known that quantum algorithms exist in this model which can achieve significant speed-ups over any possible classical algorithm; however, when f is a total function (ie. there is no promise on the input) the best quantum speed-up known is a factor of 2.

I will present several families of total boolean functions which have exact quantum query complexity which is a constant fraction of their classical query complexity. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes. I will also discuss the model of nonadaptive exact quantum query complexity, which can be characterised in terms of coding theory.

The talk will be based on the paper arXiv:1111.0475, which is joint work with Richard Jozsa and Graeme Mitchison.

A simple graph G=(V,E) is (word-)representable if there exists a word W over the alphabet V such that any two distinct letters x and y alternate in W if and only if (x,y) is an edge in E. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. It is known that a graph is representable if and only if it is k-representable for some k. The minimum k for which a representable graph G is k-representable is called its representation number.

Representable graphs first appeared in algebra, in study of the Perkins semigroup, which has played a central role in semigroup theory since 1960, particularly as a source of examples and counterexamples. However, these graphs have connections to robotic scheduling and they are interesting from combinatorial and graph theoretical point of view (for example, representable graphs are a generalization of circle graphs, which are exactly 2-representable graphs).

Some questions one can ask about representable graphs are as follows. Are all graphs representable? How do we characterize those graphs that are (non-)representable? How many representable graphs are there? How large can the representation number be for a graph on n nodes?

In this talk, we will go through these and some other questions stating what progress has been made in answering them. In particular, we will see that a graph is representable if and only if it admits a so-called semi-transitive orientation. This allows us to prove a number of results about representable graphs, not least that 3-colorable graphs are representable. We also prove that the representation number of a graph on n nodes is at most n, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as there are graphs whose representation number is n/2.

There are only a few methods for analysing the rate of convergence of an ergodic Markov chain to its stationary distribution. One is the canonical path method of Jerrum and Sinclair. This method applies to Markov chains which have no negative eigenvalues. Hence it has become standard practice for theoreticians to work with lazy Markov chains, which do absolutely nothing with probability 1/2 at each step. This must be frustrating for practitioners, who want to use the most efficient Markov chain possible.

I will explain how laziness can be avoided by the use of a twenty-year old lemma of Diaconis and Stroock's, or my recent modification of that lemma. Other relevant approaches will also be discussed. A strength of the new result is that it can be very easy to apply. We illustrate this by revisiting the analysis of Jerrum and Sinclair's well-known chain for sampling perfect matchings of a graph.

Consider the generic situation that we have to select k alternatives from a given ground set, where each element in the ground set has a random arrival time and cost. Once we have done our selection, we will greedily select the first arriving alternative, and the total cost is the time we had to wait for this alternative plus its random cost. Our motivation to study this problem comes from public transportation, where each element in the ground set might correspond to a bus or train, and the usual user behavior is to greedily select the first option from a given set of alternatives at each stop. We consider the arguably most natural arrival time distributions for such a scenario: exponential distributions, uniform distributions, and distributions with mon. decreasing linear density functions. For exponential distributions, we show how to compute an optimal policy for a complete network, called a shortest path with alternatives, in O(n(log n + δ^3)) time, where n is the number of nodes and δ is the maximal outdegree of any node, making this approach practicable for large networks if δ is relatively small. Moreover, for the latter two distributions, we give PTASs for the case that the distribution supports differ by at most a constant factor and only a constant number of hops are allowed in the network, both reasonable assumptions in practice. These results are obtained by combining methods from low-rank quasi-concave optimization with fractional programming. We finally complement them by showing that general distributions are NP-hard.

Given positive integers k and r where 4 divides k and k/2 ≤ r ≤ k-2, we give a minimum r-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is essentially best possible and improves on work of Pikhurko, who gave an asymptotically exact result. Our approach makes use of the Hypergraph Removal Lemma as well as a structural result of Keevash and Sudakov relating to the Turan number of the expanded triangle. This is joint work with Yi Zhao.

Robust optimization is an approach for optimization under uncertainty that has recently attracted attention both from theory and practitioners. While there is an elaborate and powerful machinery for continuous robust optimization problems, results on robust combinatorial optimization and robust linear integer programs are still rare and hardly general. We consider robust counterparts of integer programs and combinatorial optimization problems, i.e., seek solutions that stay feasible if at most Γ-many parameters change within a given range.

We show that one can optimize a not necessarily binary, cost robust problem, for which one can optimize a slightly modified version of the deterministic problem. Further, in case there is a ρ-approximation for the modified deterministic problem, we give a method for the cost robust counterpart to attain a (ρ+ε)-approximation (for minimization problems; for maximization we get a 2ρ-approximation), or again a ρ-approximation in a slightly more restricted case. We further show that general integer linear programs where a single or few constraints are subject to uncertainty can be solved, in case the problem can be solved for constraints on piecewise linear functions. In case these programs are binary, it suffices to solve the underlying non-robust program (n+1) times.

We demonstrate the applicability of our approach on two classes of integer programs, namely, totally unimodular integer programs and integer programs with two variables per inequality. Further, for combinatorial optimization problems our method yields polynomial time approximations and pseudopolynomial, exact algorithms for robust Unbounded Knapsack Problems.

This is joint work with Kai-Simon Goetzmann (TU Berlin) and Claudia Telha (MIT).

The Tutte polynomial of a graph is two-variable polynomial that captures many interesting properties of the graph. In this talk, I will describe the polynomial and then discuss the complexity of computing the sign of the polynomial. Having fixed the two parameters, the problem is, given an input graph, determine whether the value of the polynomial is positive, negative, or zero. We determine the complexity of this problem over (most of) the possible settings of the parameters. Surprisingly, for a large portion of the parameter space, the problem is #P-complete. (This is surprising because the problem feels more like a decision problem than a counting problem --- in particular, there are only three possible outputs.) I'll discuss the ramifications for the complexity of approximately evaluating the polynomial. As a consequence, this resolves the complexity of computing the sign of the chromatic polynomial. Here there is a phase transition at q=32/27, which I will explain. The talk won't assume any prior knowledge about graph polynomials or the complexity of counting.

(Joint work with Mark Jerrum.)

Tropical linear algebra is an emerging and rapidly evolving area of idempotent mathematics, linear algebra and applied discrete mathematics. It has been designed to solve a class of non-linear problems in mathematics, operational research, science and engineering. Besides the main advantage of dealing with non-linear problems as if they were linear, the techniques of tropical linear algebra enable us to efficiently describe complex sets, reveal combinatorial aspects of problems and view the problems in a new, unconventional way. Since 1995 we have seen a remarkable expansion of this field following a number of findings and applications in areas as diverse as algebraic geometry, phylogenetics, cellular protein production, the job rotation problem and railway scheduling.

We will give an overview of selected combinatorial aspects of tropical linear algebra with emphasis on set coverings, cycles in digraphs, transitive closures and the linear assignment problem. An application to multiprocessor interactive systems and a number of open problems will be presented.

The analysis of complex networks like the webgraph, social networks, metabolic networks or transportation networks is a challenging problem. One problem that has drawn a significant amount of attention is the question to classify the domain to which a given network belongs, i.e. whether it is, say, a social network or a metabolic network. One empirical approach to solve this problem uses the concept of network motifs. A network motif is a subgraph that appears more frequently in a certain class of graphs than in a random graph. This approach raises the theoretical question about the structural properties we can learn about a graph by looking at small subgraphs and how one can analyze graph structure by looking at random samples, as these will typically contain frequent subgraphs.

Obviously, it is not possible to to analyze classical structural properties like, for example, connectivity by only looking at small subgraphs. One needs a relaxed and more robust definition of graph properties. Such a definition is given by the concept of property testing. In my talk and within the framework of property testing I will give a partial answer to the question what we can learn about graph properties from the distribution of constant sized subgraphs. I will show that every planar graph with constant maximum degree is defined up to epsilon n edges by its distribution (frequency) of subgraphs of constant size. This result implies that every property of planar graphs is testable in the property testing sense.

(Joint work with Ilan Newman)

In the weighted k-set packing problem, we are given a collection of k-element sets, each with a weight, and seek a maximum weight collection of pairwise disjoint sets. In this talk, we consider a generalization of this problem in which the goal is to find a pairwise disjoint collection of sets that maximizes a monotone submodular function.

We present a novel combinatorial algorithm for the problem, which is based on the notion of non-oblivious local search, in which a standard local search process is guided by an auxiliary potential function distinct from the problem's objective. Specifically, we use a potential function inspired by an algorithm of Berman for weighted maximum independent set in (k+1)-claw free graphs. Unfortunately, moving from the linear (weighted) case to the monotone submodular case introduces several difficulties, necessitating a more nuanced approach. The resulting algorithm guarantees a (k + 3)/2 approximation, improving on the performance of the standard, oblivious local search algorithm by a factor of nearly 2 for large k.

More generally, we show that our algorithm applies to all problems that can be formulated as k-exchange systems, which we review in this talk. This class of independence systems, introduced by Feldman, Naor, Schwartz, and Ward, generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Such problems include matroid k-parity in strongly base orderable matroids, independent set in (k + 1)-claw free graphs (which includes k-set packing as a special case), k-uniform hypergraph b-matching, and maximum asymmetric traveling salesperson (here, k = 3). Our non-oblivious local search algorithm improves on the current state-of-the-art approximation performance for many of these specific problems, as well.

The research community has focussed on the use of heuristics and meta-heuristic methods to solve real life scheduling problems, as such problems are too large to solve exactly. However there is much to learn and utilise from exact models. This talk will explain how hybridising exact methods within heuristic techniques can enable better solutions to be obtained. Specifically, exact methods will be used to ensure that feasible solutions are guaranteed, allowing the heuristic to focus on improving secondary objectives.

Two test cases will be described. The first is a nurse rostering problem where a knapsack model is used to ensure feasibility, allowing a tabu search method to locate high quality solutions. The second is the problem of allocating medical students to clinical specialities over a number of time periods. A network flow model is hybridised within a Greedy Randomised Adaptive Search Procedure framework. It will be demonstrated that this produces better solutions than using GRASP on its own.

Stable marriage and roommates problems are the classic approach to model resource allocation with incentives and occupy a central position in the intersection of computer science and economics. There are a number of players that strive to be matched in pairs, and the goal is to obtain a stable matching from which no pair of players has an incentive to deviate. In many applications, a player is not aware of all other players and must explore the population before finding a good match. We incorporate this aspect by studying stable matching under dynamic locality constraints in social networks. Our interest is to understand local improvement dynamics and their convergence to matchings that are stable with respect to their imposed information structure in the network.

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.

The quadratic assignment problem (QAP) is a well studied and notoriously hard combinatorial optimisation problem both from the theoretical and the practical point of view. Other well known combinatorial optimisation problems as for example the travelling salesman problem or the linear arrangement problem can be seen as special cases of the QAP.

In this talk we will first introduce the problem and briefly review some important computational complexity results. Then we will focus on polynomially solvable special cases and introduce structural properties of the coefficient matrices of the QAP which guarantee the efficient solvability of the problem.

We will show that most of these special cases have the so called constant permutation property, meaning that the optimal solution of the problem does not depend on the concrete realization of the coefficient matrices as soon as those matrices possess the structural properties which turn the QAP polynomially solvable as mentioned above. We will show that the borderline between hard and easy special cases is quite thin, in the sense that slight perturbations of the structural properties mentioned above are enough to produce NP-hard special cases again. We will conclude with an outlook of further research and some open special cases which could be well worth analysing next in terms of computational complexity.

Applying the polyhedral method to a combinatorial optimization problem usually requires a description of the convex hull P of the set of feasible solutions. Typically, P is determined by an exponential number of inequalities, and a complete description is often hopeless, even for polynomial-time solvable problems. In some cases, P can be represented in a simpler way as the projection of some polyhedron Q in a higher-dimensional space, where often Q is defined by a much smaller system of constraints than P. In this talk we discuss techniques to obtain extended formulations for combinatorial optimization problems, and cases where extended formulations prove useful.

The work presented includes papers with M. Conforti, A. Del Pia, B. Gerards, and L. Wolsey.

In this talk, I will present the results on parametric analysis of the power of pre-emption for two and three uniform machines, with the speed of the fastest machine as a parameter. For identical parallel machines, I will present a series of results on the impact that adding an extra machine may have on the makespan and the total completion time. For the latter models, the solution approaches to the problem of the cost-optimal choice of the number of machines are reported.

Markov decision processes (MDPs) are powerful tools for decision making in uncertain dynamic environments. However, the solutions of MDPs are of limited practical use due to their sensitivity to distributional model parameters, which are typically unknown and have to be estimated by the decision maker. To counter the detrimental effects of estimation errors, we consider robust MDPs that offer probabilistic guarantees in view of the unknown parameters. To this end, we assume that an observation history of the MDP is available. Based on this history, we derive a confidence region that contains the unknown parameters with a pre-specified probability 1-β. Afterwards, we determine a policy that attains the highest worst-case performance over this confidence region. By construction, this policy achieves or exceeds its worst-case performance with a confidence of at least 1-β. Our method involves the solution of tractable conic programs of moderate size.

We say that a hypergraph is stable if each sufficiently large subset of its vertices either spans many hyperedges or is very structured. Hypergraphs that arise naturally in many classical settings posses the above property. For example, the famous stability theorem of Erdős and Simonovits and the triangle removal lemma of Ruzsa and Szemerédi imply that the hypergraph on the vertex set E(K_n) whose hyperedges are the edge sets of all triangles in K_n is stable. In the talk, we will present the following general theorem: If (H_n)_n is a sequence of stable hypergraphs satisfying certain technical conditions, then a typical (i.e., uniform random) m-element independent set of H_n is very structured, provided that m is sufficiently large. The above abstract theorem has many interesting corollaries, some of which we will discuss. Among other things, it implies sharp bounds on the number of sum-free sets in a large class of finite Abelian groups and gives an alternate proof of Szemerédi's theorem on arithmetic progressions in random subsets of integers.

Joint work with Noga Alon, József Balogh, and Robert Morris.

In 1975, Mike Fredman showed that, given a set of distinct values satisfying an arbitrary partial order, one can finish sorting the set in a number of comparisons equal to the information theory bound (Opt) plus at most 2n. However, it appeared that determining what comparisons to do could take exponential time. Shortly after this several people, including myself, wondered about the complementary problem Fredman's "starting point" of arranging elements into a given partial order. My long term conjecture was that one can do this, using a number of comparisons equal to the information theory lower bound for the problem plus a lower order term plus O(n) through a reduction to multiple selection. Along the way some key contributions to the problems were made, including the development of graph entropy and the work of Andy Yao (1989) and Jeff Kahn and Jeong Hang Kim (1992). The problems were both solved, with Jean Cardinal, Sam Fiorini, Gwen Joret, Raph Jungers (2009, 2010), using the techniques of graph entropy, multiple selection and merging in polynomial time to determine the anticipated Opt + o(Opt) + O(n) comparisons. The talk will discuss this long term development and some amusing stops along the way.

Counting the number of distinct copies of a given pattern in a graph can be a difficult problem when the sizes of both the pattern and the graph get large. This talk will review statistical mechanics approaches to some instances of this problem, focusing in particular on the enumeration of large matchings and long circuits of a graph. The outcomes of these methods are conjectures on the typical number of such patterns in large random graphs, and heuristic algorithms for counting and constructing them. In the case of the matchings, the heuristic statistical mechanics method has been also turned into a mathematically rigorous proof.

The modular decomposition is a powerful tool for describing combinatorial structures (such as graphs, tournaments, posets or permutations) in terms of smaller ones. Since its appearance in a talk by Fraisse in the 1950s, and first appearance in print by Gallai in the 1960s, it has appeared in a wide variety of settings ranging from game theory to combinatorial optimisation.

In this talk, after discussing some of these various historical settings, I will present a number of different settings where the modular decomposition has influenced my own research, including the enumeration and structural theory of permutations (in particular the general study of well-quasi-ordering), and -- quite unrelatedly -- recent connections made with the celebrated reconstruction conjecture.

Of increasing importance to this work has been our growing understanding of the "prime" structures: those that cannot be broken down into smaller structures under the modular decomposition. Started by Schmerl and Trotter in the early 1990s, there is now an industry of researchers looking at the fine structure of these objects, and I will present some recent work in this area. Taker a "broader" view, we also know, in the case of permutations, a Ramsey-theoretic result for these prime structures: every sufficiently long prime permutation must contain a subpermutation belonging to one of three families. However, it still remains to translate this result into one for graphs, and I will close by exploring some of the difficulties and differences discovered in our attempts to make this conversion.

Random geometric graphs have been well studied over the last 50 years or so. These are graphs that are formed between points randomly allocated on a Euclidean space and any two of them are joined if they are close enough. However, all this theory has been developed when the underlying space is equipped with the Euclidean metric. But, what if the underlying space is curved?

The aim of this talk is to initiate the study of such random graphs and lead to the development of their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We will discuss some typical structural features of these random graphs as well as some applications, related to their potential as a model for networks that emerge in social life or in biological sciences.

Given a set of points P in R^3, what is the best line that approximates P? We introduce a notion of approximation which is robust under the perturbations of P, and analyse how good it is.

Algorithmic metatheorems guarantee that certain types of problems have efficient algorithms. A classical example is the theorem of Courcelle asserting that every MSOL property can be tested in linear time for graphs with bounded tree-width. Another example is a result of Frick and Grohe that every FOL property can be tested in almost linear time in graph classes with locally bounded tree-width. Such graph classes include planar graphs or graphs with bounded maximum degree. An example of an FOL property is the existence of a fixed graph as a subgraph.

We extend these results in two directions:

• we show that FOL properties can be tested in linear time for classes of graphs with bounded expansion (this is a joint result with Zdenek Dvorak and Robin Thomas), and
• FOL properties can be polynomially tested (with the degree of the polynomial independent of the property) in classes of regular matroids with locally bounded branch-width (this is a joint result with Tomas Gavenciak and Sang-il Oum).

An alternative proof of our first result has been obtained by Dawar and Kreutzer.

We will discuss time lower bounds for both online integer multiplication and convolution in the cell-probe model. For the multiplication problem, one pair of digits, each from one of two n digit numbers that are to be multiplied, is given as input at step i. The online algorithm outputs a single new digit from the product of the numbers before step i+1. We give a lower bound of Omega((d/w)*log n) time on average per output digit for this problem where 2^d is the maximum value of a digit and w is the word size. In the convolution problem, we are given a fixed vector V of length n and we consider a stream in which numbers arrive one at a time. We output the inner product of V and the vector that consists of the last n numbers of the stream. We show an Omega((d/w)*log n) lower bound for the time required per new number in the stream. All the bounds presented hold under randomisation and amortisation. These are the first unconditional lower bounds for online multiplication or convolution in this popular model of computation.

We consider a coordination game between a sender and a receiver who communicate over a noisy channel.

The sender wants to inform the receiver about the state by transmitting a message over the channel. Both receive positive payoff only if the receiver decodes the received signal as the correct state. The sender uses a known "codebook" to map states to messages. When does this codebook define a Nash equilibrium?

The receiver's best response is to decode the received signal as the most likely message that has been sent. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed by the codebook, which is not always the case. We show two theorems that give sufficient conditions for Nash codes. First, the "best" codebook for the receiver (which gives maximum expected receiver payoff) defines a Nash code.

A second, more surprising observation holds for communication over a binary channel which is used independently a number of times, a basic model of information theory: Given a consistent tie-breaking decoding rule which holds generically, ANY codebook of binary codewords defines a Nash code. This holds irrespective of the quality of the code and also for nonsymmetric errors of the binary channel.

(Joint work with P. Hernandez)

(joint work with Vassilis Giakoumakis and Frédéric Maffray)

In a finite undirected graph G=(V,E), a vertex set Q ⊆ V is a clique separator if the vertices in Q are pairwise adjacent and G\Q has more connected components than G. An atom of G is a subgraph of G without clique separators. Tarjan and Whitesides gave polynomial time algorithms for determining clique separator decomposition trees of graphs. By a well-known result of Dirac, a graph is chordal if and only if its atoms are cliques.

A hole is a chordless cycle of length at least five. Hole-free graphs generalize chordal graphs; G is chordal if and only if it is C_4-free and hole-free. We characterize hole- and diamond-free graphs (hole- and paraglider-free graphs, respectively) in terms of the structure of their atoms. Hereby a diamond is K_4-e, and a paraglider is the result of substituting an edge into one of the vertices of a C_4; equivalently, it is the complement graph of the disjoint union of P_2 and P_3. Thus, hole- and paraglider-free graphs generalize chordal graphs and are perfect. Hole- and diamond-free graphs generalize chordal bipartite graphs (which are exactly the triangle-free hole-free graphs).

Our structural results have various algorithmic implications. Thus, the problems Recognition, Maximum Independent Set, Maximum Clique, Coloring, Minimum Fill-In, and Maximum Induced Matching can be solved efficiently on hole- and paraglider-free graphs.

Telecommunication network design has been an extremely fruitful area for the application of discrete mathematics and optimization. To cover for uncertain demands, traffic volumes are typically highly overestimated. In this talk, we adapt the methodology of robust optimization to obtain more resource- and cost-efficient network designs. In particular, we generalize valid inequalities for network design to the robust network design problem, and report on their added value.

We present a cutting-plane scheme based on the separation of some product-type classes of valid inequalities for the max-cut problem. These include triangle, odd clique, rounded psd and gap inequalities. In particular, gap inequalities were introduced by Laurent & Poljak and include many other known inequalities as special cases. Yet, they have received little attention so far and are poorly understood. This paper presents the first ever computational results, showing that gap inequalities yield extremely strong upper bounds in practice.

Joint work with Professor Adam N. Letchford and Dr. Konstantinos Kaparis, Lancaster University.

Using the notion of polynomial time reduction computer scientists have discovered an astonishingly rich web of interrelationships among the myriad computational problems that arise in diverse applications. These relationships can be used both to give evidence of intractability, such as that of NP-completeness, as well as to provide efficient algorithms.

In this talk we discuss a notion of a holographic reduction that is more general than the traditional one in the following sense. Instead of locally mapping solutions one-to-one, it maps them many-to-many but preserves some measure such as the sum of the solutions. One application is to finding new polynomial time algorithms where none was known before. Another is to give evidence of intractability. There are pairs of related problems that can be contrasted in this manner. For example, for a skeletal version of Cook’s 3CNF problem (restricted to be planar and where every variable occurs twice positively) the problem of counting the solutions modulo 2 is NP-hard, but counting them modulo 7 is polynomial time computable. Holographic methods have proved useful in establishing dichotomy theorems, which offer a more systematic format for distinguishing the easy from the probably hard. Such theorems state that for certain wide classes of problems every member is either polynomial time computable, or complete in some class conjectured to contain intractable problems.

Many practical problems can be formulated in the language of matroids and submodular functions. Objective functions of many optimization problems are submodular. Such functions also model "economies of scale" and "law of diminishing returns" in a natural way. We study the problem of maximizing a submodular function subject to k matroid constraints. We show how our analytic framework can be adapted for various types of submodular functions such as symmetric, monotone or linear. We show that the local search algorithm has performance guarantee of roughly 2/k for the matroid hypergraph matching problem where k is the size of the largest hyperedge. In the end of the talk, we will discuss randomized rounding algorithms for matroid intersection and matroid base polytops with additional constraints (or objectives) that can be represented as polynomial constraints. While the measure concentration phenomenon is well-studied in probability theory, the concentration of polynomial functions of independent random variables is a relatively recent development (Kim- Vu (2000)). Our randomized rounding is inherently dependent, so we need to prove our own concentration inequalities for such processes. We will discuss multiple applications of such concentration bounds in optimization.

In this talk an analysis of the popular push-pull protocol for spreading a rumor on networks will be presented. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on two models of random graphs that have a power law degree distribution with an arbitrary exponent β > 2. In particular, we study preferential attachment graphs and random graphs with a given expected degree sequence.

The main findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 < β < 3, then the rumor spreads to almost all nodes in Ω(loglog n) rounds with high probability. This is exponentially faster than all previously known upper bounds for the push-pull protocol established for various classes of networks. On the other hand, if β > 3, then Ω(log n) rounds are necessary.

I will also discuss the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes.

This is joint work with N. Fountoulakis, T. Sauerwald.

In our talk, we shall concentrate on a classical problem of combinatorial geometry going back to P. Erdős and G. Szekeres. First of all, we shall introduce and discuss the minimum number g(n) such that from any set of g(n) points in general position in the plane, one can choose a set of n points which are the vertices of a convex n-gon. Further, we shall proceed to multiple important modifications of the quantity g(n). In particular we shall consider a value h(n): it’s definition is almost the same as the just-mentioned definition of g(n); one should only replace in it “a convex n-gon” by “a convex empty n-gon”. Also we shall generalize h(n) to h(n, k) and to h(n, mod q), where the previous condition “an n-gon is empty” is substituted either by the condition “an n-gon contains at most k points” (so that h(n) = h(n, 0)) or by the condition “an n-gon contains 0 points modulo q”. Finally, we shall speak about various chromatic versions of the above quantities.

We shall present a series of recent achievments in the field, and we shall discuss some new approaches and conjectures.

We consider the following variant of the classical pattern matching problem motivated by the increasing amount of digital data we need to store: given an uncompressed pattern s[1..m] and a compressed representation of a string t[1..N], does s occur in t? I will present a high-level description of an optimal linear time algorithm which detects the occurrence in t compressed using the Lempel-Ziv-Welsch method (widely used in real-life applications due to its simplicity and relatively good approximation ratio), thus answering a question of Amir, Benson, and Farach from 1994. Then I will show how to extend this method to solve the fully compressed version of the problem, where both the pattern and the text are compressed, also in optimal linear time, hence improving the previously known solution of Gąsieniec and Rytter, and essentially closing this line of research.

In this talk I will present results of my ongoing research whose goal is to understand kernelizability of the multiway cut problem. To make the talk self-contained, I will start from the definition of kernelization, accompanied by a simple kernelization procedure for the Vertex Cover problem. Then I will define the multiway cut problem, briefly overview the existing parameterization results, and provide reasons why understanding kernelizability of the problem is an interesting question.

In the final part of my talk I will present a kernelization algorithm for a special, yet NP-hard, case of the multiway cut problem and discuss possible ways of its generalization.

A vertex-colouring of a graph is an assignment of colours to the vertices of the graph so that adjacent vertices receive different colours. The minimum number of colours needed for such a colouring is called the chromatic number of the graph. Now suppose that certain vertices are already pre-coloured, and we want to extend this partial colouring to a colouring of the whole graph. Because of the pre-coloured vertices, we may need more colours than just the chromatic number. How many extra colours are needed under what conditions has been well-studied, and we will give a short overview of those results.

A different way of colouring the vertices is so-called fractional colouring. For such a colouring we are given an interval [0,K] of real numbers, and we need to assign to each vertex a subset of [0,K] of measure one so that adjacent vertices receive disjoint subsets. The fractional chromatic number is the minimum K for which this is possible.

Again we can look at this problem assuming that certain vertices are already pre-coloured (are already assigned a subset of measure one). Assuming some knowledge about the pre-coloured vertices, what K is required to guarantee that we can always extend this partial colouring to a fractional colouring of the whole graph? The answer to this shows a surprising dependence on the fractional chromatic number of the graph under consideration.

This is joint work with Dan Kral, Martin Kupec, Jean-Sebastien Sereni and Jan Volec.

It is well known and easy to prove that every graph with m edges has a cut containing at least m/2 edges. While the complete graph shows that the constant ½ cannot be improved, Edwards established a more precise extremal bound that includes lower order terms. The problem of determining such bounds is called the extremal maxcut problem and many variants of it have been studied. In the first part of the talk, we consider a natural analogue of the extremal maxcut problem for posets and some of its generalisations. (Whereas a graph cut is a set of all edges that cross some bipartition of the graph’s vertex set, we shall define a poset cut to be a set of all comparable pairs that cross some order-preserving partition of the poset’s ground set.)

The algorithmic maxcut problem for graphs, i.e. the problem of determining the size of the largest cut in a graph, is well known to be NP-hard. In the second part of the talk, we examine the complexity of the poset analogue of the max-cut problem and some of its generalisations.

By a classical result of Tait, the four color theorem is equivalent to the statement that each 2-edge-connected 3-regular planar graph has a 3-edge-coloring. An embedding of a graph into a surface is called polyhedral if its dual has no multiple edges or loops. A conjecture of Grunbaum, presented in 1968, states that each 3-regular graph with a polyhedral embedding into an orientable surface has a 3-edge-coloring. With respect to the result of Tait, it aims to generalize the four color theorem for any orientable surface. We present a negative solution to this conjecture, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable graph with a polyhedral embedding into the surface.

It is widely believed that certain simple modifications of the random graph process lead to discontinuous phase transitions. In particular, starting with the empty graph on $n$ vertices, suppose that at each step two pairs of vertices are chosen uniformly at random, but only one pair is joined, namely one minimizing the product of the sizes of the components to be joined. Making explicit an earlier belief of Achlioptas and others, in 2009, Achlioptas, D'Souza and Spencer conjectured that there exists a δ>0 (in fact, δ\ge 1/2) such that with high probability the order of the largest component `jumps' from o(n) to at least δ n in o(n) steps of the process, a phenomenon known as `explosive percolation'. We give a simple proof that this is not the case. Our result applies to all `Achlioptas processes', and more generally to any process where a fixed number of independent random vertices are chosen at each step, and (at least) one edge between these vertices is added to the current graph, according to any (online) rule. We also prove the existence and continuity of the limit of the rescaled size of the giant component in a class of such processes, settling a number of conjectures. Intriguing questions remain, however, especially for the product rule described above.

Joint work with Oliver Riordan.

In his seminal work Kauffman introduced a very simple dynamical model of biological gene-regulatory networks. Each gene was modeled by a binary variable that can be in an ON/OFF state and interacts with other genes via a coupling Boolean function which determines the state of a gene at the next time-step. It was argued that this model, also known as Random Boolean network (RBN) or Kauffman net, is relevant to the understanding of biological systems. RBNs belong to a larger class of Boolean networks that exhibits a rich dynamical behavior, which is very versatile and has found its use in the modeling of genetic, neural and social networks as well as in many other branches of science.

The annealed approximation has proved to be a valuable tool in the analysis of large scale Boolean networks as it allows one to predict the time evolution of network activity (proportion of ON/OFF states) and Hamming distance (the difference between the states of two networks of identical topology) order parameters. The broad validity of the annealed approximation to general networks of this type has remained an open question; additionally, while the annealed approximation provides accurate activity and Hamming distance results for various Boolean models with quenched disorder it cannot compute correlation functions, used in studying memory effects. In particular, there are models with strong memory effects where the annealed approximation is not valid in specific regimes.

In the current work we study the dynamics of a broad class of Boolean networks with quenched disorder and thermal noise using the generating functional analysis; the analysis is general and covers a large class of recurrent Boolean networks and related models. We show that results for the Hamming distance and network activity obtained via the quenched and annealed approaches, for this class, are identical. In addition, stationary solutions of Hamming distance and two-time autocorrelation function (inaccessible via the annealed approximation) coincide, giving insight into the uniform mapping of states within the basin of attraction onto the stationary states. In the presence of noise, we show that above some noise level the system is always ergodic and explore the possibility of spin-glass phase below this level. Finally, we show that our theory can be used to study the dynamics of models with strong memory effects.

Joint work with Alexander Mozeika

In the Traveling Salesman Problem (TSP) we are given a collection of cities and the distance between each pair, and asked to find the shortest route that visits all the cities and returns to its starting place. When writers in the popular press wish to talk about NP-completeness, this is the problem they typically use to illustrate the concept, but how typical is it really? The TSP has also been highly attractive to theorists, who have proved now-classical results about the worst-case performance of heuristics for it, but how relevant to practice are those results?

In this talk I provide a brief introduction to the TSP, its applications, and key theoretical results about it, and then report on experiments that address both the above questions. I will concentrate on randomly generated instances with cities uniformly distributed in the unit square, which I will argue provide a reasonable surrogate for the instances arising in many real-world TSP applications. I'll first survey the performance of heuristics on these instances, and then report on an ongoing study into the average length and structure of their optimal tours, based on extensive data generated using state-of-the-art optimization software for the TSP, which can regularly find optimal solutions to TSP instances with 1000 cities or more.

Scheduling problems with batching machines are extensively considered in the literature. Batching means that sets of jobs which are processed on the same machine must be grouped into batches. Two types of batching machines have been considered, namely s-batching machines and p-batching machines. For s-batching machines, the processing time of a batch is given by the sum of the processing times of the jobs in the batch, whereas, for p-batching machines the processing time of batches is given by the maximum of the processing times of the jobs in the batch.

In this talk we consider no-wait flowshop scheduling problems with batching machines. The first problem that will be considered is no-wait flowshop with two p-batching machines and three batching machines. For these problems we characterize the optimal solution and we give a polynomial time algorithm to minimize the makespan for the two-machine problem. For the three-machine problem we show the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. The second problem that will be considered is the no-wait flowshop with two-machines, where the first machine is a p-batching machine, and the second machine is an s-batching machine. We show that the makespan minimization is NP-hard and we present some polynomial cases by reducing the scheduling problem to a matching problem with minimal cost in a specific graph.

A (geometric) fullerene is a 3-valent polyhedron whose faces are hexagons and pentagons (so, 12 of them). A fullerene is said to be Frank-Kasper if its hexagons are adjacent only to pentagons; there are four such fullerenes: with 20, 24, 26 and 28 vertices.

A space fullerene is a 4-valent 3-periodic tiling of R^3 by Frank-Kasper fullerenes. Space fullerenes are interesting in Crystallography (metallic alloys, zeolites, clathrates) and in Discrete Geometry. 27 such physical structures, all realized by alloys, were already known.

A new computer enumeration method has been devised for enumerating the space fullerenes with a small fundamental domain under their translation groups: 84 structures with at most 20 fullerenes in the reduced unit cell (i.e. by a Biberbach group) were found. The 84 obtained structures have been compared with the 27 physical ones and all known special constructions: by Frank-Kasper-Sullivan, Shoemaker-Shoemaker, Sadoc-Mossieri and Deza-Shtogrin. 13 obtained structures are among the above 27, including A_{15}, Z, C_{15} and 4 other Laves phases.

Moreover, there are 16 new proportions of 20-, 24-, 26-, 28-vertex fullerenes in the unit cell. 3 of them provide the first counterexamples to a conjecture by Rivier-Aste, 1996, and to the old conjecture by Yarmolyuk-Kripyakevich, 1974, that the proportion should be a conic linear combination of proportions (1:3:0:0), (2:0:0:1), (3:2:2:0) of A_{15}, C_{15}, Z.

So, a new challenge to practical Crystallography and Chemistry is to check the existence of alloys, zeolites, or other compounds having one of the 71 new geometrical structures.

This is joint work with Mathieu Dutour and Olaf Delgado.

Given q \in \mathbb{N} and R \subset \mathbb{N}, an (R,q)-polycycle is a non-empty, 2-connected, planar, locally finite (i.e. any circle contains only a finite number of its vertices) graph G with faces partitioned into two non-empty sets F_1 and F_2, so that:

1. all elements of F_1 (called proper faces) are combinatorial i-gons with i \in R,
2. all elements of F_2 (called holes, the exterior face(s) are amongst them) are pair-wise disjoint, i.e. have no common vertices,
3. all vertices have degree within {2,...,q} and all interior (i.e. not on the boundary of a hole) vertices are q-valent.

Such a polycycle is called elliptic, parabolic or hyperbolic when 1/q+1/r-1/2 (where r={max_{i \in R}i}) is positive, zero or negative, respectively.

A bridge of an (R,q)-polycycle is an edge, which is not on a boundary and goes from a hole to a hole (possibly the same hole). An (R,q)-polycycle is called elementary if it has no bridges. An open edge of an (R,q)-polycycle is an edge on a boundary, such that each of its end-vertices has degree less than q. Every (R,q)-polycycle is formed by the agglomeration of elementary (R,q)-polycycles along their open edges.

We classify all elliptic elementary (R,q)-polycycles and present various applications.

A family of graphs F on a fixed set of n vertices is said to be `triangle-intersecting' if for any two graphs G and H in F, the intersection of G and H contains a triangle. Simonovits and S\'{o}s conjectured that such a family has size at most $\frac{1}{8}2^{{n \choose 2}}$, and that equality holds only if F consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then $|F| \leq \tfrac{1}{8} 2^{{n \choose 2}}$. Equality holds only if $F$ consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results from the theory of Boolean functions. We will then discuss some related open questions.

All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).

An r-multicolouring of a graph allocates r colours (from some `palette') to each vertex of a graph such that the colour sets at adjacent vertices are disjoint; in an (r,\lambda) overlap colouring the sets at adjacent vertices must also overlap by \lambda colours. The (r,\lambda) chromatic number, \chi_{r,\lambda}(G), is the smallest possible palette size. Classifying graphs by their overlap chromatic properties turns out to be strictly finer than by their multichromatic properties but not as fine as by their cores.

I shall survey what is currently known: basically, everything concerning series-parallel (i.e. K_4-minor-free) and wheel graphs, and the asymptotics for complete graphs.

The interrelationship between numerical representations and data structures is efficacious. However, in many write-ups such connection has not been made explicit. As far as we know, their usage was first discussed in the seminar notes by Clancy and Knuth. Early examples of data structures relying on number systems include finger search trees and binomial queues.

In this talk, we survey some known number systems and their usage in existing worst-case efficient data structures. We formalize properties of number systems and requirements that should be imposed on a number system to guarantee efficient performance on the corresponding data structures. We introduce two new number systems: the strictly-regular system and the five-symbol skew system. We illustrate how to perform operations on the two number systems and give applications for their usage to implement worst-case efficient data structures. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit flips.

The strictly-regular system is a compact system that supports increments and decrements in constant number of digit flips. Compared to other number systems, the strictly-regular system has distinguishable properties. It is superior to the regular system for its efficient support of decrements, and superior to the extended-regular system for being more compact by using three symbols instead of four. To demonstrate the applicability of the new number system, we modify Brodal's meldable priority queues making delete require at most 2lg(n)+O(1) element comparisons (improving the bound from 7lg(n)+O(1)) while maintaining the efficiency and the asymptotic time bounds for all operations.

The five-symbol skew system also supports increments and decrements with a constant number of digit flips. In this number system the weight of the ith digit is 2ⁱ-1, and hence it can be used to implement efficient structures that rely on complete binary trees. As an application, we implement a priority queue as a forest of heap-ordered complete binary trees. The resulting data structure guarantees O(1) worst-case cost per insert and O(lg(n)) worst-case cost per delete.

The Constraint Satisfaction Problem (CSP) is concerned with the feasibility of satisfying a collection of constraints. The CSP paradigm has proven to be useful in many practical applications.

In a CSP instance, a set of variables must be assigned values from some domain. The values allowed for certain (ordered) subsets of the variables are restricted by constraint relations. The general CSP is NP-hard. However there has been considerable success in identifying tractable fragments of the CSP: these have traditionally been characterised in one of two ways:

The sets of variables that are constrained in any CSP instance can be abstracted to give a hypergraph structure for the instance. Subproblems defined by limiting the allowed hypergraphs are called structural. The theory of tractable structural subproblems is analogous to the theory of tractable conjunctive query evaluation in relational databases and many of the tractable cases derive from generalisations of acyclic hypergraphs. We have several important dichotomy theorems for the complexity of structural subproblems.

Alternatively, it is possible to restrict the set of relations which can be used to define constraints. Subproblems defined in this way are called relational. It turns out that the complexity of relational subproblems can be studied by analysing a universal algebraic object: the clone of polymorphisms. This algebraic analysis is well advanced and again there are impressive dichotomy theorems for relational subproblems.

As such, it is timely to consider so-called hybrid subproblems which can neither be characterised by structural nor relational restrictions. This exciting new research direction shows considerable promise. In this talk we present several of the new results (tractable classes) for hybrid tractability: Turan, Broken Triangle, Perfect and Pivots.

The Internet enabled sponsored market has been one of those that have been attracting extensive attention. Within this framework of a new market design, the price and allocation of on-line advert placement through auction or market equilibrium become very important topic both in theory and in practice.

Within this context, we discuss incentive issues of both the market maker (the seller) and the market participants (the buyers) within the market equilibrium paradigm, and discuss existence, convergence and polynomial time solvability results with the comparison to auction protocols.

We present a near-linear time algorithm that approximates the edit distance between two strings within a significantly better factor than previously known. This result emerges in our investigation of edit distance from a new perspective, namely a model of asymmetric queries, for which we present near-tight bounds.

Another consequence of this new model is the first rigorous separation between edit distance and Ulam distance, by tracing the hardness of edit distance to phenomena that were not used by previous analyses.

[Joint work with Alexandr Andoni and Krzysztof Onak.]

We will consider the most general ternary Permutation Constraint Satisfaction Problem (CSP) and observe that all other ternary Permutation-CSPs can be reduced to this one. An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering alpha of V that maximises the number of triples whose ordering (under alpha) follows that of the constraint.

We prove that all ternary Permutation-CSPs parameterized above average (which is a tight lower bound) have kernels with a quadratic number of variables.

Much interest is currently being expressed in "Real-world" VRPs. But what are they and how can they be defined? The conventional method of problem formulations for the VRP are rarely extended to deal with many real-world constraints and rapidly become complex and unwieldy as the number and complexity of constraints increases. In Software Engineering practice, complex systems and constraints are commonplace, and the prevailing modelling and programming paradigm is Object-Oriented Programming. This talk will present an OOP model for the VRP and show it's application to some classic VRP variants as well as some real-world problem domains.

To reserve your place please contact Sue Shaw <S.Shaw@wbs.ac.uk>.

The mathematical study of the transmission of information without error was initiated by Shannon in the 50s. Only in 1979, Lovasz solved the major open problem of Shannon concerned with this topic. The solution is based on a now well-known object called the Lovasz theta function. Its role greatly contributed to the developments of areas of Mathematics like semidefinite programming and extremal problems in combinatorics. The Lovasz theta function is an upper bound to the zero-error capacity, however it is not always tight.

In the last two decades quantum information theory established itself as the natural extension of information theory to the quantum regime, i.e. for the study of information storage and transmission with the use of quantum systems and dynamics. I will show that the Lovasz theta function is an upper bound to the zero-error capacity when the parties of a channel can share certain quantum physical resources. This quantity, which is called entanglement-assisted zero-error capacity, can be greater than the classical zero-error capacity, in both single use of the channel and asymptotically.

Additionally, I will propose a physical interpretation of the Lovasz theta function as the maximum violation of certain noncontextual inequalities. These are inequalities traditionally used to study the difference between classical, quantum mechanical, and more exotic theories of nature.

This is joint work with Adan Cabello (Sevilla), Runyao Duan (Tsinghua/Sydney), and Andreas Winter (Bristol/Singapore).

A mixed graph G=(V;D,L) is a graph G together with a bipartition (D,L) of its edge set. A d-dimensional direct-length framework (G,p) is a mixed graph G together with a map p:V->R^d. We imagine that the vertices are free to move in R^d subject to the constraints that the directions of the direction edges and the lengths of the length edges edges remain constant. The framework is rigid if the only such motions are simple translations.

Two frameworks (G,p) and (G,q) are equivalent if the edges in D have the same directions and edges in L have the same lengths in both (G,p) and (G,q). The framework (G,p) is globally rigid if every framework which is equivalent to (G,p), can be obtained from (G,p) by a translation or a dilation by -1. It is bounded if there exists K in R such that every framework (G,q) which is equivalent to (G,q), satisfies |q(u)-q(v)| <= K for all u,v in V.

I will describe characterizations of boundedness and rigidity of generic 2-dimensional direction-length frameworks, and give partial results for the open problem of characterizing the global rigidity of such frameworks. This is joint work with Peter Keevash and Tibor Jordán.

Matrix griddings are structural means of representing permutations as built of finitely many increasing and decreasing permutations. More specifically, let M be an m × n matrix with entries m_{ij} ∈ { 0,1,-1}. We say that a permutation π admits an M-gridding if the xy-plane in which the graph Γ of π has been plotted can be partitioned into an xy-parallel, m × n rectangular grid with cells C_{ij}, such that the following hold:

• if m_{ij} = 1 then Γ ∩ C_{ij} is an increasing sequence of points;
• if m_{ij} = -1 then Γ ∩ C_{ij} is decreasing;
• if m_{ij} = 0 then Γ ∩ C_{ij} = ∅.

Let G(M) denote the set (pattern class) of all permutations which admit M-griddings. Grid classes have been present in the pattern classes literature from very early on. For example, Atkinson (1999) observed that the class of permutations avoiding 321 and 2143 is equal to G((1 1)) ∩ G((1 1)^t) and used this to enumerate the class. Much more recently, grid classes have played a crucial role in Vatter's (to appear) classification of small growth rates of pattern classes.

These past uses hint strongly at the natural importance of grid classes in the general theory of pattern classes. If this is to be so, the next step is to establish `nice' general properties of grid classes themselves. A number of researchers, including M.H. Albert, M.D. Atkinson, M. Bouvel, R. Brignall, V. Vatter and myself, have been engaged on such a project over the past year, and I will report on their findings. The results are proved by an intriguing interplay of language-theoretic and combinatorial-geometric methods, the flavour of which I will try to convey. The talk will conclude with a discussion of some open problems concerning general grid classes, which ought to point the way for the next stage in this project.

It is well known that there is a sharp density threshold for a random r-SAT formula to be satisfiable, and a similar, smaller, threshold for it to be satisfied by the pure literal rule. Also, above the satisfiability threshold, where a random formula is with high probability (whp) unsatisfiable, the unsatisfiability is whp due to a large ``minimal unsatisfiable subformula'' (MUF).

By contrast, we show that for the (rare) unsatisfiable formulae below the pure literal threshold, the unsatisfiability is whp due to a unique MUF with smallest possible ``excess'', failing this whp due to a unique MUF with the next larger excess, and so forth. In the same regime, we give a precise asymptotic expansion for the probability that a formula is unsatisfiable, and efficient algorithms for satisfying a formula or proving its unsatisfiability. It remains open what happens between the pure literal threshold and the satisfiability threshold. We prove analogous results for the k-core and k-colorability thresholds for a random graph, or more generally a random r-uniform hypergraph.

A theorem of Tutte characterises all graphs that contain a perfect matching. In contrast, a result of Garey and Johnson implies that the decision problem of whether an r-uniform hypergraph contains a perfect matching is NP-complete for r>2. So it is natural to seek simple sufficient conditions that ensure a perfect matching. Given an r-uniform hypergraph H, the degree of a k-tuple of vertices is the number of edges in H containing these vertices. The minimum vertex degree of H is the minimum of these degrees over all 1-tuples. The minimum codegree of H is the minimum of all the degrees over all (r-1)-tuples of vertices in H.

In recent years there has been significant progress on this problem. Indeed, in 2009 Rödl, Ruciński and Szemerédi characterised the minimum codegree that ensures a perfect matching in an r-uniform hypergraph. However, much less is known about minimum vertex degree conditions for perfect matchings in r-uniform hypergraphs H. Hàn, Person and Schacht gave conditions on the minimum vertex degree that ensures a perfect matching in the case when r>3. These bounds were subsequently lowered by Markström and Ruciński. This result, however, is believed to be far from tight. In the case when r=3, Hàn, Person and Schacht asymptotically determined the minimum vertex degree that ensures a perfect matching. In this talk we discuss a result which determines this threshold exactly. This is joint work with Daniela Kühn and Deryk Osthus.

An incidentor in a directed or undirected multigraph is an ordered pair of a vertex and an arc incident to it. It is convenient to treat an incidentor as half of an arc incident to a vertex. Two incidentors of the same arc are called mated. Two incidentors are adjacent if they adjoin the same vertex. The incidentor coloring problem (indeed, a class of problems) is to color all incidentors of a given multigraph with the minimum number of colors satisfying some restrictions on colors of adjacent and mated incidentors.

A review of various results on incidentor coloring will be given in the talk.

Assume that the vertex set of a graph G is partitioned into blocks B_1, B_2, ... of size r>1, so that B_i contains vertices labelled (i-1)r+1, (i-1)r+2, ... , ir. The r-empire chromatic number of G is the minimum number of colours \chi_r(G) needed to colour the vertices of G in such a way that all vertices in the same block receive the same colour, but pairs of blocks connected by at least one edge of G are coloured differently.The decision version of this problem (termed the r-empire colouring problem) dates back to the work of Perci Heawood on the famous Four Colour Theorem (note that the 1-empire colouring problem is just planar graph colouring). In this talk I will present a survey of some old and new results on this problem. Among other things, I will focus on the computational complexity of the r-empire colouring problem and then talk about the colourability of random trees.

There are three classical unsolved reconstruction problems: vertex reconstruction of S.M. Ulam and P.J. Kelly (1941), edge reconstruction of F. Harary (1964) and switching reconstruction of R.P. Stanley (1985). It turns out that these and similar questions are intimately connected with a wide range of important and also mostly open problems related to polynomials. For example, a simplest analogue of vertex reconstruction - reconstruction of a sequence from its subsequences leads to Littlewood-type problems concerning polynomials with -1,0, 1 coefficients. In switching reconstruction one has to know the number of zero coefficients in the expansion of (1-x)^n (1+x)^m, which is the same as the number of integer zeros of Krawtchouk polynomials. In this talk I will try to explain these connections and show how they can be applied to reconstruction.

We study the following question: given a finite collection of graphs G_1,...,G_k, decide whether the dominating set problem is NP-hard in the class of (G_1,...,G_k)-free graphs or not. In this talk, we prove the existence of an efficient algorithm that answers this question for k=2.

We consider the problem of finding a maximal matching of minimum size in a graph, and in particular, in bipartite regular graphs. This problem was motivated by a stable marriage allocation problem. The minimum maximal matching is known to be NP-hard in bipartite graphs with maximum degree 3. We first extend this result to the class of $k$-regular bipartite graphs, for any fixed $k\geq 3$. In order to find some “good” solutions, we compare the size $M$ of a maximum matching and the size $MMM$ of a minimum maximal matching in regular graphs. It is well known that $M\leq 2MMM$ in any graph and we show that it can be improved to $M\leq (2-1/k)MMM$ in $k$-regular graphs. On the other hand, we analyze a greedy algorithm finding in $k$-regular bipartite graphs a maximal matching of size $MM$ satisfying $MM\leq (1-\epsilon(k))M$. It leads to a $(1-\epsilon(k))(2-1/k)$-approximation algorithm for $k$-regular bipartite graphs.

This is joint work with Tinaz Ekim and C. Tanasescu

We investigate the problem of "local reconstruction", as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of "message reconstruction", where given an oracle access to a corrupted encoding $w \in \{0,1\}^n$ of some message $x \in \{0,1\}^k$ our goal is to probabilistically recover $x$ (or some portion of it). This should be done by a procedure (reconstructor) that given an index $i$ as input, probes $w$ at few locations and outputs the value of $x_i$. The reconstructor can (and indeed must) be randomized, but all its randomness is specified in advance by a single random seed, such that with high probability ALL $k$ values $x_i$ for $1 \leq i \leq k$ are reconstructed correctly.

Using the reconstructor as a filter allows to evaluate certain classes of algorithms on $x$ efficiently. For instance, in case of a parallel algorithm, one can initialize several copies of the reconstructor with the same random seed, and they can autonomously handle decoding requests while producing outputs that are consistent with the original message $x$. Another example is that of adaptive querying algorithms, that need to know the value of some $x_i$ before deciding which index should be decoded next.

The second problem that we address is "codeword reconstruction", which is similarly defined, but instead of reconstructing the message our goal is to reconstruct the codeword itself, given an oracle access to its corrupted version.

Error correcting codes that admit message and codeword reconstruction can be obtained from Locally Decodable Codes (LDC) and Self Correctible Codes (SCC) respectively. The main contribution of this paper is a proof that in terms of query complexity, these are close to be the best possible constructions, even when we disregard the length of the encoding.

This is joint work with Eldar Fischer and Arie Matsliah.

We study the effects of introducing altruistic agents into atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the framework of congestion games with player-specific latency functions. Stable states are the pure Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. In general, pure Nash equilibria are often absent and existence is \NP-hard to decide. Perhaps surprisingly, if all delay functions are linear, the games remain potential games even when agents are arbitrarily altruistic. This result can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples.

In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior.

The problem of allocating resources in proportion to some measure has been studied in various fields of science for a long time. The apportionment problem of allocating seats in a parliament in proportion to the number of votes obtained by political parties is one example. This presentation will show a number of other real-life problems, for instance the Liu-Layland problem, stride scheduling and fair queueing which can be formulated and solved as the problems of proportional optimization and fairness.

We consider a stochastic optimization problem involving protection of vital arcs in a critical path network. We analyze a problem in which task finishing times are uncertain, but can be insured a priori to mitigate potential delays. We trade off costs incurred in insuring arcs with expected penalties associated with late completion times, where lateness penalties are lower semi-continuous nondecreasing functions of completion time. We provide decomposition strategies to solve this problem with respect to either convex or nonconvex penalty functions. In particular, we employ the Reformulation-Linearization Technique to make the problem amenable to solution via Benders decomposition. We also consider a chance-constrained version of this problem, in which the probability of completing a project on time is sufficiently large.

Energy usage has become a major issue in the design of microprocessors, especially for battery-operated devices. Many modern processors support dynamic speed scaling to reduce energy usage. The speed scaling model assumes that a processor, when running at speed s, consumes energy at the rate of s^\alpha, where \alpha is typically 2 or 3. In older days when speed scaling was not available, energy reduction was mainly achieved by allowing a processor to enter a low-power sleep state, yet waking up requires extra energy. It is natural to study job scheduling on a processor that allows both sleep state and speed scaling. In the awake state, a processor running at speed s>0 consumes energy at the rate s^\alpha + \sigma , where \sigma > 0 is the static power and s^\alpha is the dynamic power. In this case, job scheduling involves two components: a sleep management algorithm to determine when to work or sleep, and a speed scaling algorithm to determine which job to run and at what speed to run. Adding a sleep state changes the nature of speed scaling. Without sleep state, running a job slower is a natural way to save energy. With sleep state, one can also save energy by working faster to allow a longer sleep period. It is not trivial to strike a balance. In this talk, we will discuss some new scheduling results involving both speed scaling and sleep management.

Edge expansion for graphs is a well-studied measure of connectivity, which is important in discrete mathematics and computer science. While there has been much recent work done in finding approximation algorithms for determining edge expansion, there has been less attention in developing exact polynomial-time algorithms to determine edge expansion for restricted graph classes. In this talk, I will present an algorithm that, given an n-vertex graph G of genus g, determines the edge expansion of G in time n^{O(g)}.

We survey some crucial techniques in approximating connectivity problems. The most general question we study is the Steiner Network problem, where we are given an undirected weighted graph with costs on the edges, and required number r_ij of paths between every i, j. The paths need to be vertex or edge disjoint depending on the problem. The goal is to find a minimum cost feasible solution.

The full talk has the following techniques and problems:

1. Solving k out-connectivity in polynomial time in the edge (Edmonds) and in the vertex (Frank Tardos) cases. This gives a simple ratio 2 for edge k-connectivity.
2. The cycle lemma of Mader: together with technique 1 it both gives results for minimum power k-connectivity power problems (see the talk for exact definition) and an improved result for k-edge connectivity in the metric case.
3. Laminarity and the new charging scheme by Ravi et. al. getting a much simplified version of Jain's theorem of 2 approximating of Steiner network in the edge disjoint paths case.

The king of refinements of Nash equilibrium is trembling hand perfection. In this talk, we show that it is NP-hard and SQRTSUM-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB.

We study policy iteration for infinite-horizon Markov decision processes. In particular, we study greedy policy iteration. This is an algorithm that has been found to work very well in practice, where it is used as an alternative to linear programming. Despite this, very little is known about its worst case complexity. Friedmann has recently shown that policy iteration style algorithms have exponential lower bounds in a two player game setting. We extend these lower bounds to Markov decision processes with the total-reward and average-reward optimality criteria.

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorial distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length l of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide several FPT-algorithms (for all variants) when parameterized by both k and l and hardness results when the parameter is only one of k and l. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph. Joint work with Dimitrios M. Thilikos (Athens).

The Colouring Pairs of Binary Trees problem was introduced by Gibbons and Czumaj, and its equivalence to the Four Colour Problem means that it is an interesting combinatorial problem. Given two binary trees Ti and Tj, the question is whether Ti and Tj can be 3-coloured in such a way that the edge adjacent to leaf k is the same colour in Ti and Tj. This talk will introduce the problem and discuss some of the results that have been achieved so far, and will also discuss the potential benefits of finding a general solution to the problem. In particular we present two approaches that lead to linear-time algorithms solving CPBT for specific sub-classes of tree pairs. This is joint work with Alan Gibbons.

A beautiful conjecture of Erdos-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.

The problem of portfolio selection is a standard problem in financial engineering and has received a lot of attention in recent decades. Classical mean-variance portfolio selection aims at simultaneously maximizing the expected return of the portfolio and minimizing portfolio variance, and determining all efficient (Pareto-optimal) solutions. In the case of linear constraints, the problem can be solved efficiently by parametric quadratic programming (i.e., variants of Markowitz’ critical line algorithm). However, there are many real-world constraints that lead to a non-convex search space, e.g., cardinality constraints which limit the number of different assets in a portfolio, or minimum buy-in thresholds. As a consequence, the efficient approaches for the convex problem can no longer be applied, and new solutions are needed. In this talk, we present a way to integrate an active set algorithm into a multi-objective evolutionary algorithm (MOEA). The idea is to let the MOEA come up with some convex subsets of the set of all feasible portfolios, solve a critical line algorithm for each subset, and then merge the partial solutions to form the solution of the original non-convex problem. Because this means the active set algorithm has to be run for the evaluation of every candidate solution, we also discuss how to efficiently implement parametric quadratic programming for portfolio selection. We show that the resulting envelope-based MOEA significantly outperforms other state-of-the-art MOEAs.

Privacy is a fundamental problem in modern data analysis. We describe "differential privacy", a mathematically rigorous and comprehensive notion of privacy tailored to data analysis. Differential privacy requires, roughly, that any single individual's data have little effect on the outcome of the analysis. Given this definition, it is natural to ask: what computational tasks can be performed while maintaining privacy? In this talk, we focus on the tasks of machine learning and releasing contingency tables.

Learning problems form an important category of computational tasks that generalizes many of the computations applied to large real-life datasets. We examine what concept classes can be learned by an algorithm that preserves differential privacy. Our main result shows that it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the hypothesis class. This is a private analogue of the classical Occam's razor result.

Contingency tables are the method of choice of government agencies for releasing statistical summaries of categorical data. We provide tight bounds on how much distortion (noise) is necessary in these tables to provide privacy guarantees when the data being summarized is sensitive. Our investigation also leads to new results on the spectra of random matrices with correlated rows.

Consider a scenario with a set of autonomous mobile robots having initial positions in the plane. Their goal is to move in such a way that they eventually reach a prescribed formation. Such a formation may be a straight line between two given endpoints (short communication chain), a circle or any other geometric pattern, or just one point (gathering problem). In this talk, I consider simple local strategies for such robotic formation problems: the robots are limited to see only robots within a bounded radius; they are memoryless, without common orientation. Thus, their decisions where to move next are solely based on the relative positions of robots within the bounded radius. I will present local strategies for short communication chains and gathering, and present runtime bounds assuming different time models. All previous algorithms with a proven time bound assume global view on the positions of all robots.

In 1990, Courcelle proved a fundamental theorem stating that every property of graphs definable in monadic second-order logic can be decided in linear time on any class of graphs of bounded tree-width. This theorem is the first of what is today known as algorithmic meta-theorems, that is, results of the form: every property definable in a logic L can be decided efficiently on any class of structures with property P.

Such theorems are of interest both from a logical point of view, as results on the complexity of the evaluation problem for logics such as first-order or monadic second-order logic, and from an algorithmic point of view, where they provide simple ways of proving that a problem can be solved efficiently on certain classes of structures.

Following Courcelle's theorem, several meta-theorems have been established, primarily for first-order logic with respect to properties of structures derived from graph theory. In this talk I will motivate the study of algorithmic meta-theorems from a graph algorithmic point of view, present recent developments in the field and illustrate the key techniques from logic and graph theory used in their proofs.

So far, work on algorithmic meta-theorems has mostly focused on obtaining tractability results for as general classes of graphs as possible. The question of finding matching lower bounds, that is, intractability results for monadic second-order or first-order logic with respect to certain graph properties, has so far received much less attention. Tight matching bounds, for instance for Courcelle's theorem, would be very interesting as they would give a clean and exact characterisation of tractability for MSO model-checking with respect to structural properties of the models. In the second part of the talk I will present a recent result in this direction showing that Courcelle's theorem can not be extended much further to classes of unbounded tree-width.

The use of two-player games of infinite duration has a long history in the synthesis of controllers for reactive systems. Classically, the quality of a winning strategy is measured in the size of the memory needed to implement it. But often there are other natural quality measures: in many games (even if they are zero-sum) there are winning plays for Player 0 that are more desirable than others. In this talk, we define and compute time-optimal winning strategies for three winning conditions.

In a Poset game, Player 0 has to answer request by satisfying a partially ordered set of events. We use a waiting time based approach to define the quality of a strategy and show that Player 0 has optimal winning strategies, which are finite-state and effectively computable.

In Parametric LTL, temporal operators may be equipped with free variables for time bounds. We present algorithms that determine whether a player wins a game with respect to some, infinitely many, or all variable valuations. Furthermore, we show how to determine optimal valuations that allow a player to win a game.

In a k-round Finite-time Muller game, a play is stopped as soon as some loop is traversed k times in a row. For k=n^2n!+1, the winner of the k-round Finite-time Muller game wins also the classical Muller game. For k=2, this equivalence does no longer hold. For all values in between, it is open whether the games are equivalent.

The theory of graph minors by Robertson and Seymour is one of very active fields in modern (algorithmic) graph theory. In this talk we will be interested in two containment relations similar to minors -- contractions and induced minors. We will survey known classic results and present some new work. In particular, I would like to talk about two recent results: (1) a polynomial-time algorithm for finding induced linkages in claw-free graphs, and (2) a polynomial-time algorithm for contractions to a fixed pattern in planar graphs. The talk will be based on joint work with Jiri Fiala, Bernard Lidicky, Daniel Paulusma and Dimitrios Thilikos.

One of the main aims in the theory of percolation is to find the `critical probability' above which long range connections emerge from random local connections with a given pattern and certain individual probabilities. The quintessential example is Kesten's result from 1980 that if the edges of the square lattice are selected independently with probability p, then long range connections appear if and only if p>1/2. The starting point is a certain self-duality property, observed already in the early 60s; the difficulty is not in this observation, but in proving that self-duality does imply criticality in this setting.

Since Kesten's result, more complicated duality properties have been used to determine a variety of other critical probabilities. Recently, Scullard and Ziff have described a very general class of self-dual planar percolation models; we show that for the entire class (in fact, a larger class), self-duality does imply criticality.

The Gaussian relay channel network, is a natural candidate to model wireless networks. Unfortunately, it is not known how to determine the capacity of this model, except for simple networks. For this reason, Avestimehr, Diggavi and Tse introduced in 2007 a purely deterministic network model (the ADT model), which captures two key properties of wireless channels, namely broadcast and superposition. Furthermore, the capacity of an ADT model can be determined efficiently and approximates the capacity of Gaussian relay channels. In 2009, Amaudruz and Fragouli presented the first polynomial time algorithm to determine a relay encoding strategy that achieves the min-cut value of an ADT network.

In this talk, I will present a flow model which shares many properties with classical network flows (as introduced by Ford and Fulkerson) and includes the ADT model as a special case. The introduced flow model is based on linking systems, a structure closely related to matroids. Exploiting results from matroid theory, many interesting prop result. Furthermore, classical matroid algorithms can be used to obtain efficient algorithms for finding maximum flows, minimum cost flows and minimum cuts. This is based on joint work with Michel Goemans and Satoru Iwata.

The celebrated Johnson-Lindenstrauss lemma says that every n points in Euclidean space can be represented using O(log n) dimensions with only a minor distortion of pairwise distances. It has been conjectured that a much-improved dimension reduction representation is achievable for many interesting data sets, by bounding the target dimension in terms of the intrinsic dimension of the data, e.g. by replacing the log(n) term with the doubling dimension. This question appears to be quite challenging, requiring new (nonlinear) embedding techniques.

We make progress towards resolving this question by presenting two dimension reduction theorems with similar flavour to the conjecture. For some intended applications, these results can serve as an alternative to the conjectured embedding.

[Joint work with Lee-Ad (Adi) Gottlieb.]

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, we study the k-means method in the model of smoothed analysis.

Smoothed analysis is a hybrid of worst-case and average-case analysis, which is based on a semi-random input model in which an adversary first specifies an arbitrary input that is subsequently slightly perturbed at random. This models random influences (e.g., measurement errors or numerical imprecision) that are present in most applications, and it often yields more realistic results than a worst-case or average-case analysis.

We show that the smoothed running time of the k-means method is bounded by a polynomial in the input size and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

This talk is based on joint work with David Arthur (Stanford University) and Bodo Manthey (University of Twente).

A total coloring is a combination of a vertex coloring and an edge coloring of a graph: every vertex and every edge is assigned a color and any two adjacent/incident objects must receive distinct colors. One of the main open problems in the area of graph colorings is the Total Coloring Conjecture of Behzad and Vizing from the 1960's asserting that every graph has a total coloring with at most D+2 colors where D is its maximum degree. When relaxed to fractional total colorings, the Total Coloring Conjecture was verified by Kilakos and Reed. In the talk, we will present a proof of the following conjecture of Reed:

For every real ε > 0 and integer D, there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number at most D+1+ε.

For D=3 and D=4,6,8,10,..., we prove the conjecture in a stronger form: there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number equal to D+1.

Joint work with Tomas Kaiser, František Kardoš, Andrew King and Jean-Sébastien Sereni.

A Hamilton decomposition of a graph or digraph G is a set of edge-disjoint Hamilton cycles which together contain all the edges of G. In 1968, Kelly conjectured that every regular tournament has a Hamilton decomposition. We recently proved an approximate version of this conjecture (joint work with D. Kuhn and A. Treglown).

I will also describe an asymptotic solution of a problem by Nash-Williams (from 1971) on the number of edge-disjoint Hamilton cycles in a graph with given minimum degree (joint work with D. Christofides and D. Kuhn).

We study time complexity of decision trees over an infinite set of k-valued attributes. As time complexity measures, we consider the depth and its extension - weighted depth of decision trees. The problem under consideration is the following. Is it possible for an arbitrary finite set of attributes to construct a decision tree which recognizes values of these attributes for a given input, and has the weighted depth less than the total weight of the considered attributes? The solution of this problem for the case of depth is given in terms of independence dimension (which is closely connected with VC dimension) and a condition of decomposition of granules. Each granule can be described by a set of equations of the kind "attribute = value". The solution of the considered problem for the weighted depth is based on the solution for the depth. We also discuss the place of the obtained results in the comparative analysis of time complexity of deterministic and nondeterministic decision trees.

The random triangle-free graph process starts with an empty graph and a random ordering on all the possible edges and in each step considers an edge and adds it too the graph if it remains triangle-free. In the same way one can define the random planar graph process where an edge is added when the graph remains planar. In this talk the two processes are compared. For example we show that with high probability at the end of the random planar process every fixed planar graph is a subgraph whereas in the triangle-process dense triangle-free subgraphs will not appear.

There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey some recent results of this type, including:

1. a solution to a question of Thomassen on an analogue of Dirac's theorem for oriented graphs,
2. a theorem on packing cyclic triangles in tournaments that "almost" answers a question of Cuckler and Yuster, and
3. a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan.

These are joint work respectively with (1.) Kuhn and Osthus, (2.) Sudakov, and (3.) Fox and Sudakov.

1. The problem of ergodicity for cellular automata.
2. The problem of eroders for cellular automata.

This is a joint seminar with the Centre for Complexity Science.

We consider strategies that can be used to speed-up the cover time of a random walk on undirected connected graphs. The price of this speed up is normally some extra work that can be performed locally by the walk or by the vertices of the graph. Typical assumptions about what is allowed include: Biased walk transitions, Use of previous history, Local exploration of the graph.

Methods of local exploration include the neighbour marking process RW-MARK and look-ahead RW-LOOK (searching to fixed depth).

The marking process, RW-MARK, made by a random walk on an undirected graph G is as follows. Upon arrival at a vertex v, the walk marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v.

Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by the process RW-MARK to mark all vertices of G. If, for instance G is the hypercube on n vertices the processes marks all vertices in time O(n), with high probability. This significantly reduces the n ln n cover time of the hypercube using a standard random walk.

The process RW-MARK can be compared to the marking process where a vertex v is chosen uniformly at random (coupon collecting) at each step. For the hypercube also has a marking time of O(n).

In the related look-ahead process RW-LOOK, the walk marks all neighbours of the visited vertex to some depth k. For the hypercube, for example, the performance of the processes RW-LOOK-1, and CC-LOOK-1 is asymptotic to n ln 2 with high probability.

This research is joint work with Petra Berenbrink, Robert Elsaesser, Tomasz Radzik and Thomas Sauerwald.

We consider the model of exploration of an undirected graph G by a single agent which is called the rotor-router mechanism or the Propp machine (among other names). Let p_v indicate the edge adjacent to a node v which the agent took on its last exit from v. The next time when the agent enters node v, first the "rotor" at node v advances pointer p_v to the next edge in a fixed cyclic order of the edges adjacent to v. Then the agent is directed onto edge p_v to move to the next node. It was shown before that after initial O(mD) steps, the agent periodically follows one established Eulerian cycle (that is, in each period of 2m consecutive steps the agent will traverse each edge exactly twice, once in each direction). The parameters m and D are the number of edges in G and the diameter of G. We investigate robustness of such exploration in presence of faults in the pointers p_v or dynamic changes in the graph. In particular, we show that after the exploration establishes an Eulerian cycle, if at some step k edges are added to the graph, then a new Eulerian cycle is established within O(km) steps. We show similar results for the case when the values of k pointers p_v are arbitrarily changed and when an arbitrary edge is deleted from the graph. Our proofs are based on the relation between Eulerian cycles and spanning trees known as the "BEST" Theorem (after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte).

This is joint work with: E. Bampas, L. Gasieniec, R. Klasing and A. Kosowski.

For a graph G, a signed domination function of G is a two-colouring of the vertices of G with colours +1 and -1 such that the closed neighbourhood of every vertex contains more +1's than -1's. This concept is closely related to combinatorial discrepancy theory as shown by Fueredi and Mubayi [J. Combin. Theory, Ser. B76 (1999) 223-239]. The signed domination number of G is the minimum of the sum of colours for all vertices, taken over all signed domination functions of G. In this talk, we will discuss new upper and lower bounds for the signed domination number. These new bounds improve a number of known results.

In this presentation we give an overview of applications of, and algorithms for, multi-index assignment problems (MIAPs). MIAPs, and relatives of it, have a long history both in applications as well as in theoretical results, starting at least in the 1950's. In particular, we focus here on the complexity and approximability of special cases of MIAPs.

A prominent example of a MIAP is the so-called axial three index assignment problem (3AP) which has many applications in a variety of domains including clustering. A description of 3AP is as follows. Given are three n-sets R, G, and B. For each triple in R X G X B a cost-coefficient c(i,j,k) is given. The problem is to find n triples such that each element is in exactly one triple, while minimizing total cost. We show positive and negative results for finding an optimal solution to this problem that depend upon different ways of how the costs c(i,j,k) are specified.

We consider approximating the minmax value of a multiplayer game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of "ε log n" digits (for any constant ε > 0) is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits (for any constant c ≤ 1) can be done in quasi-polynomial time.We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k = 2 and there are only two possible rational payoffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated with any polynomial number of digits of accuracy in time n^O(k). On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-CLIQUE requires time n^Ω(k) then so does minmax value computation.

This is joint work with Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, and Peter Bro Miltersen.

We consider the profit maximizing pricing problem for single-minded buyers. Here, we wish to sell a set of m items to n buyers, each of whom is interested in buying a single set of items. Our goal is to set prices for the items such that the profit obtained by selling the items to the buyers who can afford them is maximized. We also assume in our case, that we have arbitrarily many copies of each item to sell.

When the underlying set of items are edges of a graph, and the buyers are interested in buying specific paths, this is called the tollbooth problem. We consider the special case where the graph is a tree, or a path. In the case of a tree, the problem is already known to be APX-hard. We give an O(log n) approximation algorithm. When the graph is a path, the problem is called the highway problem. In this case, we show that the problem is strongly NP-hard, complementing an earlier QPTAS. We also consider the discount model where some items are allowed to have negative prices, and show that a very simple case is already APX-hard.

This is joint work with K. Elbassioni, S. Ray and R. Sitters.

Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes ("lotteries") in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? We show that the answers to these questions hinge on the exact model of consumer behavior we deploy and present several tight bounds on the increase in revenue obtainable via randomization and the computational complexity of revenue maximization in these different models. This is joint work with Shuchi Chawla, Bobby Kleinberg, and Matt Weinberg.

Multiobjective Optimization has many applications in such fields as the internet, finance, biomedicine, management science, game theory and engineering. However, solving MO problems is not an easy task. Searching for all Pareto optimal solutions is expensive and time consuming process because there are usually exponentially large (or infinite) Pareto optimal solutions. Even for the simplest problem determining whether a point belongs to the Pareto curve is NP-hard.

In this talk we are going to discuss some continuous and combinatorial multiobjective optimization problems and their applications in management, finance and military. Exact and heuristic techniques for solving these problems are presented.

We also consider nondifferentiable multiobjective programming problems involving generalized convex functions and present optimality conditions and duality results for the problems.

For a fixed graph H, let ex(n,H) be the maximum number of edges of an n-vertex graph not containing a copy of H. The asymptotic estimation of ex(n,H) is a central problem to extremal graph theory, and for the case when H is non-bipartite the answer is given by the Erdős-Stone theorem. However despite considerable effort, the problem is still open when H is bipartite.

A related topic is the study of ex(n, l × H), the maximum number of edges of an n-vertex graph not containing l-vertex disjoint copies of a graph H. Insofar, this function has been investigated only for some special values of H. In this talk I shall first discuss known results about ex(n, l × H). Then for a given α ∈ (0,1) I shall determine the asymptotic behaviour of ex(n, αn × H), in the particular case when H is a bipartite graph. The proof is an application of the regularity lemma.

This is joint work with Jan Hladký.

We introduce a "Pólya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of k urns, randomly choose c distinct urns with probability proportional to the product of a power γ > 0 of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If γ ≤ 1, the urn occupancies are asymptotically equal with probability 1. For γ > 1, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.

Fix a positive integer k, and consider the class of all graphs which do not have k+1 vertex-disjoint cycles. A classical result of Erdős and Pósa says that each such graph G contains a blocker of size at most f(k). Here a blocker is a set B of vertices such that G-B has no cycles. We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set 1,...,n have a blocker of size k. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph R_n taken uniformly at random from the class: we see for example that the probability that R_n is connected tends to a specified limit as n → ∞. There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles. This is joint work with Valentas Kurauskas and Mihyun Kang.

Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph G=(V,E) is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.

We show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of Ω(log n/loglog n) for this model when the aggregation function agg is an L_p-norm.

Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the L_p-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. can be viewed as solving this problem in the L₁-norm while the result on congestion minmizing oblivious routing solves it for L_∞. We give a single proof that shows the existence of a good tree-based oblivious routing for any L_p-norm.

We present two algorithms for counting the number of colourings of sparse random graph. Our approach is based on correlation decay techniques originating in statistical physics.

The first algorithm is based on establishing correlation decay properties of Gibbs distribution which are related to Dobrushin's condition for uniqueness of Gibbs measure on infinite trees. More specifically, we impose boundary conditions to a specific set of vertices of the graph and we show that the effect of this boundary decays as we move away.

For the second algorithm we set a new context for exploiting correlation decay properties. Instead of imposing boundary conditions -fixing the colouring of vertices-, we impose a specific graph structure to some region (i.e. delete edges) and show that the effect of this change on the Gibbs distribution decays as we move away. It turns out that this approach designates a new set of spatial correlation decay conditions that can be used for counting algorithms.

In both cases the algorithms with high probability provide in polynomial time a (1/poly(n))-approximation of the logarithm of the number of k-colourings of the graph ("free energy") with k constant. The value of k depends on the expected degree of the graph. The second technique gives better results than the first one in terms of minimum number of colours needed.

Finally, the second algorithm can be applied to another class of graphs which we call locally a-dense graphs of bounded maximum degree Δ. A graph G = (V, E) in this family has following property: For all {u,v} in E the number of vertices which are adjacent to v but not adjacent to u are at most (1-a)Δ, where 0<a<1 is a parameter of the model. For a locally a-dense graph G with bounded Δ the algorithm computes in polynomial time a (1/polylogn)-approximation to the logarithm of the number of k-colourings, for k> (2-a)Δ. By restricting the treewidth of the neighbourhoods in G we can improve the approximation.

The analogue of hereditary properties of graphs for permutations are known as "permutation classes", defined as downsets in the "permutation containment" partial ordering. They are most commonly described as the collection "avoiding" some set of permutations, cf forbidden induced subgraphs for hereditary graph properties. Their origin lies with Knuth in the analysis of sorting machines, but in recent years have received a lot of attention in their own right. While much of the emphasis has been on exact and asymptotic enumeration of particular families of classes, an ongoing study of the general structure of permutations is yielding remarkable results which typically also have significant enumerative consequences.

In this talk I will describe a number of these structural results, with a particular emphasis on the question of partial well-order -- i.e. the existence or otherwise of infinite antichains in any given permutation class. The building blocks of all permutations are "simple permutations", and we will see how these on their own contribute to the partial well-order problem. We will see how "grid classes", a seemingly independent concept used to express large complicated classes in terms of smaller easily-described ones, also have significant consequences in determining the existence of infinite antichains. Finally, I will present recent and ongoing work in combining these two concepts, both to describe a general method of constructing antichains and to prove when certain classes are partially well-ordered.

We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a two-player win-lose (zero-sum) game that we call the wiretap game. The value of this game is the greatest probability that the wiretapper can secure for hitting the virtual network. The value is shown to be equal the reciprocal of the strength of the underlying graph. We provide a polynomial time algorithm that finds linear-sized description of the maxmin-polytope, and a characterization of its extreme points. It also provides a succint representation of all equilibrium strategies of the wiretapper that minimize the number of pure best responses of the hider. Among these strategies, we efficiently compute the unique strategy that maximizes the least punishment that the hider incurs for playing a pure strategy that is not a best response.

Finally, we show that this unique strategy is the nucleolus of the recently studied simple cooperative spanning connectivity game.

Joint work with: Haris Aziz, Mike Paterson and Rahul Savani.

A reset word for a finite deterministic automaton is a word which takes the machine to a fixed state from any starting state. Investigations into an old conjecture on the length of a reset word (if one exists) has led to new properties of permutation groups lying between primitivity and 2-transitivity, and a surprising fact about the representation of transformation monoids as endomorphism monoids of graphs. In the talk I will discuss some of these things and their connections.

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the local pooling conditions are satised, GMS achieves 100% throughput. A graph G = (V,E) is said to satisfy the local pooling conditions if for every induced subgraph H of G there exists a function g : V(H) → [0, 1] such that Σ_v∈S g(v)=1 for every maximal stable set S in H.

We first analyze line graphs and give a characterization of line graphs that satisfy local pooling. Line graphs are of interest since they correspond to the interference graphs of wireless networks under primary interference constraints. Finally we consider claw-free graphs and give a characterization of claw-free graphs that satisfy local pooling. This is joint work with Berk Birand, Maria Chudnovsky, Paul Seymour, Gil Zussman and Yori Zwols.

Online algorithms studied in theory are characterized by the fact that they get to know the input sequence incrementally, one job at a time, and a new job is not issued until the previous one is processed by the algorithm. In real applications, jobs can usually be delayed for a short amount of time. As a consequence, the input sequence of jobs can be reordered in a limited fashion to optimize the performance. In this talk, the power and limits of this online reodering paradigm is discussed for several problems.

Let X be the number of triangles in a random graph G(n,1/2). Loebl, Matousek and Pangrac showed that X is close to uniformly distributed modulo q when q=O(log n) is prime. We extend this result considerably, and discuss further implications of our methods for the distribution of X. This is joint work with Atsushi Tateno (Oxford).

If A is a set of n positive integers, how small can the set {a/(a,b) : a,b ∈ A} be? Here as usual (a,b) denotes the HCF of a and b. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set A of n points in Z^d, how small can (A-A)⁺, the projection of the difference set of A onto the positive orthant, be?

Freiman and Lev gave an example to show that (in any dimension) the size can be as small as n^2/3 (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least n^2/3, and asked if this held in any dimension. Holzman, Lev and Pinchasi showed that in three dimensions the size is at least n^3/5, and that in four dimensions the size is at least n^6/11 (up to a logarithmic factor), and they also asked if the correct exponent is always 2/3.

After some background material, the talk will focus on recent developments, including a negative answer to the n^2/3 question.

Joint work with Béla Bollobás.

Circulant graphs form an important and very well-studied class of graph. They are Cayley graphs of cyclic groups and have been proposed for numerous applications such as local area computer networks, large area communication networks, parallel processing architectures, distributed computing, and VLSI design. Their connectivity and diameter, cycle and path structure, and further graph-theoretical properties have been studied in great detail. Polynomial time algorithms for isomorphism testing and recognition of circulant graphs have been long-standing open problems which were completely solved only recently.

Our goal here is to extend some of the fundamental results concerning circulant graphs to the similarly defined yet more general class of distance graphs. We prove that the class of circulant graphs coincides with the class of regular distance graphs. We study the existence of long cycles and paths in distance graphs and analyse the computational complexity of problems related to their connectivity and diameter.

Joint work with L. Draque Penso und J.L. Szwarcfiter.

A graph has low discrepancy if its global edge distribution is "close" to that of a random graph with the same overall density. It has been known that low discrepancy is related to the spectra of various matrix representations of the graph such as the adjacency matrix or the normalized Laplacian. More precisely, a large spectral gap implies low discrepancy. The topic of this talk is the converse implication: does low discrepancy imply a large spectral gap? The proofs are based on the Grothendieck inequality and the duality theorem for semidefinite programs.

We introduce the study of social context games. A social context game is defined by an underlying game in strategic form, and a social context consisting of an undirected graph of neighborhood among players and aggregation functions. The players and strategies in a social context game are as in the underlying game, while the players' utilities in a social context game are computed from their payoffs in the underlying game based on the graph of neighborhood and the aggregation functions. Examples of social context games are ranking games and coalitional con- gestion games. A signifcant challenge is the study of how various social contexts affect various properties of the game. In this work we consider resource selection games as the underlying games, and four basic social contexts. An important property of resource selection games is the existence of pure strategy equilibrium. We study the existence of pure strategy Nash equilibrium in the corresponding social context games. We also show that the social context games possessing pure strategy Nash equilibria are not potential games, and therefore are distinguished from congestion games.

Joint work with Itai Ashlagi and Moshe Tennenholtz.

The problem of reaching consensus in a distributed environment is one of the fundamental topics in the area of distributed computing, systems and architectures. It was formally abstracted in late 70's by Lamport, Pease and Shostak. The early work on this problem focused on feasibility, i.e., what are the conditions under which the consensus can be solved. Later, the complexity of solutions has become of great importance. In this talk I'll introduce the problem, present selected classic algorithms and lower bounds, and conclude with my recent work on time and communication complexity of consensus in a message-passing system.

For a connected graph G = (V, E), a subset U of vertices is called a k-cut if U disconnects G, and the subgraph induced by U contains exactly k≥1 components. More specifically, a k-cut U is called a (k, l)-cut if V \ U induces a subgraph with exactly l≥2 components. We study two decision problems, called k-CUT and (k, l)-CUT, which determine whether a graph G has a k-cut or (k, l)-cut, respectively. By pinpointing a close relationship to graph contractibility problems we first show that (k, l)-CUT is in P for k=1 and any fixed constant l≥2, while the problem is NP-complete for any fixed pair k, l≥2. We then prove that k-CUT is in P for k=1, and NP-complete for any fixed k≥2. On the other hand, we present an FPT algorithm that solves (k, l)-CUT on planar graphs when parameterized by k + l. By modifying this algorithm we can also show that k-CUT is in FPT (with parameter k) and DISCONNECTED CUT is solvable in polynomial time for planar graphs. The latter problem asks if a graph has a k-cut for some k≥2.

Joint work with Takehiro Ito and Marcin Kamiński.

This is a survey talk about counting/sampling contingency tables and cell-bounded contingency tables. In the cell-bounded contingency tables problem, we are given a list of positive integer row sums r=(r₁,...,r_m), a list of positive integer column sums c=(c₁,...,c_n), and a non-negative integer bound b_ij, for every 1 ≤ i ≤ m, 1 ≤ j ≤ n.

The problem is to count/sample the set of all m-by-n tables X ∈ Z^mn of non-negative integers which satisfy the given row and column sums, and for which 0 ≤ X_ij ≤ b_ij for all i, j. I will outline a complicated (reduction to volume estimation) algorithm for approximately counting these tables in polynomial time, when the number of row is constant. I also hope to outline a more recent, 'cute' dynamic programming algorithm for exactly the same case of constantly-many rows. The case for general m is still open.

Joint with Martin Dyer and Dana Randall

The Ramsey number R(l x H) is the smallest integer m such that any l-colouring of the edges of K_m induces a monochromatic copy of H. We prove that R(4 x P_n)=2.5n+o(n). Luczak proposed a way how to attack the problem of finding a long monochromatic path in a coloured graph G: one should search for a large monochromatic connected matching in the reduced graph of G. Here we propose a modification of Luczak's technique: we find a large monochromatic connected fractional matching. This relaxation allows us to use LP duality and reduces the question to a vertex-cover problem.

This is a joint work with Jan Hladký and Daniel Král'.

Random graphs G on n vertices and with edge probability at least c(log n/n)^(1/Δ) are robust in the following sense: Let H be an arbitrary planar bipartite graph on (1-ε)n vertices with maximum degree Δ. Now you, the adversary, may arbitrarily delete edges in G such that no vertex looses more than a third of its neighbours. However, you will not be able to destroy all copies of H.

This result is obtained (joint work with Yoshiharu Kohayakawa and Anusch Taraz) via a sparse version of the regularity lemma. In the talk I will provide some background concerning related results, introduce sparse regularity, and outline how this can be used to prove theorems such as the one above.

An important instance of the Caccetta-Häggkvist conjecture asserts that an n-vertex digraph with minimum outdegree at least n/3 contains a directed triangle. Improving on a previous bound of 0.3532n due to Hamburger, Haxell, and Kostochka we prove that a digraph with minimum outdegree at least 0.3465n contains a directed triangle. The proof is an application of a recent combinatorial calculus developed by Razborov. This calculus enables one to formalize common techniques in the area (such as induction or the Cauchy-Schwartz inequality). In the talk I shall describe Razborov's method in general, and its application to the setting of the Cacceta-Häggvist Conjecture.

This is joint work with Dan Král' and Sergey Norin.

Szemerédi's regularity lemma is a powerful tool in extremal graph theory, which had have many applications. In this talk we present several variants of Szemerédi's original lemma (due to several researchers including Frieze and Kannan, Alon et al., and Lovász and Szegedy) and discuss their relation to each other.

We consider the problem of periodic graph traversal in which a mobile entity with constant memory has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in minimization of the length of the exploration period.

This problem is unsolvable if the local port numbers are set arbitrarily (shown by Budach in 1978). However, surprisingly small periods can be achieved when carefully assigning the local port numbers. Dobrev, Jansson, Sadakane, and Sung described an algorithm for assigning port numbers, and an oblivious agent (i.e. an agent with no memory) using it, such that the agent explores all graphs with n vertices within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was later proved to be no more than 3.75n (using a different assignment of the port numbers). Following on from this, a period of length at most (4 1/3)n was shown for oblivious agents, and a period of length at most 3.5n for agents with constant memory.

This talk describes results in two papers by the speaker, which are joint work with several other authors.

I will discuss the problem of cutting the (discrete or continuous) d-dimensional torus economically, so that no nontrivial cycle remains. This improves, simplifies and/or unifies results of Bollobás, Kindler, Leader and O'Donnell, of Raz and of Kindler, O'Donnell, Rao and Wigderson. More formal, detailed abstract(s) appear in http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf and in http://www.math.tau.ac.il/~nogaa/PDFS/torusone.pdf.

Joint work with Bo'az Klartag.

In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference Plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the "physical model" and is the established way of modelling interference in the engineering community. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.

We study oblivious power assignments in which the power value of a pair only depends on the distance between the points of this pair. We prove that oblivious power assignments cannot yield approximation ratios better than Ω(n) for the directed version of the problem, which is the worst possible performance guarantee as there is a straightforward algorithm that achieves an O(n)-approximation. For the bidirectional version, however, we can show the existence of a universally good oblivious power assignment: For any set of n bidirectional communication requests, the so-called "square root assignment" admits a coloring with at most polylog(n) times the minimal number of colors. The proof for the existence of this coloring is non-constructive. We complement it by an approximation algorithm for the coloring problem under the square root assignment. This way, we obtain the first polynomial time algorithm with approximation ratio polylog(n) for interference scheduling in the physical model.

This is joint work with Alexander Fanghänel, Thomas Keßelheim and Harald Räcke

The Traveling Salesman Problem (TSP) is one of the most famous NP-hard problems. So, much works have been done to study polynomially solvable cases, that is, to find good conditions for distances between cities such that an optimal tour can be found in polynomial time. These good conditions give some restriction on the optimal solution, for example, Monge property. For a given complete weighted digraph G, a vertex x of G, and a positive integer k, the Vehicle Routing Problem (VRP) is to find a minimum weight connected subgraph F of G such that F is a union of k cycles sharing only the vertex x. In this talk, we apply good conditions for the TSP to the VRP. We will show that if a given weighted digraph satisfies several conditions, which is known for the TSP, then an optimal solution of the VRP can also be computed in polynomial time.

Consider a firm, called the buyer, that satisfies its demand over a T-period time horizon by assigning the demand vector to a supplier via a procurement (reverse) auction; call this the Standard auction. The firm is considering an alternative procedure in which it will allow bids on one or more periods; in this auction, there can be more than one winner covering the demand vector; call this the Multiple Winner auction. Choosing the Multiple Winner auction over the Standard auction will tend to: (1) allow each supplier the option of supplying demand for any subset of periods of the T-period horizon; (2) increase competition among the suppliers, and (3) allow the buyer to combine bids from different suppliers in order to lower his purchase cost. All three effects might lead one to expect that the buyer's cost will always be lower in the Multiple Winner auction than in the Standard auction. To the contrary, there are cases in which the buyer will have a higher cost in the Multiple Winner auction. We provide a bound on how much greater the buyer's cost can be and show that this bound is sharp.

The identification of functional modules in protein-protein interaction networks is an important topic in systems biology. These modules might help, for example, to better understand the underlying biological mechanisms of different tumor subtypes. In this talk, I report on results of a cooperation with statisticians and medical researchers from the University of Würzburg. In particular, I will present an exact integer linear programming solution for this problem, which is based on its connection to the well-known prize-collecting Steiner tree problem from Operations Research.

I will decribe a family of finitely presented, but infinite-state, stochastic models that arise by adding a natural recursion feature to Markov Chains, Markov Decision Processes, and Stochastic Games.

These models subsume a number of classic and heavily studied purely stochastic models, including (multi-type) branching processes, (quasi-)-birth-death processes, stochastic context-free grammars, and others. They also provide a natural abstract model of probabilistic procedural programs with recursion.

The theory behind the algorithmic analysis of these models, developed over the past few years, has turned out to be very rich, with connections to a number of areas of research. I will survey just a few highlights from this work. There remain many open questions about the computational complexity of basic analysis problems. I will highlight a few such open problems.

(Based on joint work with Mihalis Yannakakis, Columbia University)

For a given undirected graph G, the Network Loading Problem (NLP) deals with the design of a least cost network by allocating discrete units of facilities with different capacities on the links of G so as to support expected pairwise demands between some endpoints of G. In this work, we relax the assumption of known demands and study robust NLP with polyhedral demands to obtain designs flexible enough to support changing communication patterns in the least costly manner. More precisely, we seek for a final design that remains operational for any feasible demand realization in a prescribed polyhedral set.

Firstly, we give a compact multi-commodity formulation of the problem for which we prove a nice decomposition property obtained from projecting out the flow variables. This simplifies the resulting polyhedral analysis and computations considerably by doing away with metric inequalities, an attendant feature of the most successful algorithms on the Network Loading Problem. Then, we focus on a specific choice of the uncertainty description, called the "hose model", which specifies aggregate traffic upper bounds for selected endpoints of the network. We study the polyhedral aspects of the Network Loading Problem under hose demand uncertainty and present valid inequalities for robust NLP with arbitrary number of facilities and arbitrary capacity structures as the second main contribution of the present work. Finally, we develop an efficient Branch-and-Cut algorithm supported by a simple but effective heuristic for generating upper bounds and use it to solve several well-known network design instances.

We study the design of optimal mechanisms in a setting where job-agents compete for being processed by a service provider that can handle one job at a time. Each job has a processing time and incurs a waiting cost. Jobs need to be compensated for waiting. We consider two models, one where only the waiting costs of jobs are private information (1-d), and another where both waiting costs and processing times are private (2-d). An optimal mechanism minimizes the total expected expenses to compensate all jobs, while it has to be Bayes-Nash incentive compatible. We derive closed formulae for the optimal mechanism in the 1-d case and show that it is efficient for symmetric jobs. For non-symmetric jobs, we show that efficient mechanisms perform arbitrarily bad. For the 2-d case, we prove that the optimal mechanism in general does not even satisfy IIA, the "independent of irrelevant alternatives" condition. We also show that the optimal mechanism is not even efficient for symmetric agents in the 2-d case.

Joined work with Birgit Heydenreich, Debasis Mishra and Marc Uetz.

Communication networks (such as the Internet or BT's network) are held together by a wide variety of interacting network control systems. Examples include routing protocols, which determine the paths used by different sessions, and flow control mechanisms, which determine the rate at which different sessions can send traffic. Many of these control processes can be viewed as distributed algorithms that aim to solve a network-wide optimisation problem.

I will present a mathematical framework, based on Lagrangian decomposition, for the design and analysis of such algorithms. As an illustration, I will discuss how this framework has been used in BT Innovate to develop a new resource control system which integrates multi-path routing and admission control decisions.

The notion of convexity plays an important role in convergence proofs for our algorithms. We can design a control system with stability guarantees as long as the system's target behaviour can be captured as the solution to a convex optimisation problem. Unfortunately, many standard network design problems are formulated as integer programming problems and therefore inherently non-convex. I will discuss some of the implications of this non-convexity and identify some related research challenges.

We discuss bounds on extremal sets for problems like those below:

1. What is the largest subset of (ℤ/nℤ)^r that does not contain an arithmetic progression of length k?
2. What is the largest subset/(multiset) of (ℤ/nℤ)^r that does not contain n elements that sum to 0?
3. What is the largest subset of [1,...,n]^r that does not contain a solution of x+y=z (i.e., which is a sum free set)?
4. Colour the elements of [1,...,n]^r red and blue. How many monochromatic Schur triples are there?

A matrix is called Monge, if its density matrix is nonnegative. Monge matrices play an important role in optimisation. Distance multiplication (also known as min-plus or tropical multiplication) of two Monge matrices of size n can be performed in time O(n²). Motivated by applications to string comparison, we introduced in a previous work the following subclass of Monge matrices. A matrix is called unit-Monge, if its density matrix is a permutation matrix; we further restrict our attention to a subclass that we call simple unit-Monge matrices. Our previous algorithm for distance multiplication of simple unit-Monge matrices runs in time O(n^3/2). Landau conjectured in 2006 that this problem can be solved in linear time. In this work, we give an algorithm running in time O(n log⁴ n), thus approaching Landau's conjecture within a polylogarithmic factor. The new algorithm implies immediate improvements in running time for a number of string comparison and graph algorithms: semi-local longest common subsequences between permutations; longest increasing subsequence in a cyclic permutation; longest pattern-avoiding subsequence in a permutation; longest piecewise monotone subsequence; maximum clique in a circle graph; subsequence recognition in a grammar-compressed string; sparse spliced alignment of genome strings.

The notion of a boundary graph property is a relaxation of that of a minimal property. Several fundamental results in graph theory have been obtained in terms of identifying minimal properties. For instance, Robertson and Seymour showed that there is a unique minimal minor-closed property with unbounded tree-width (the planar graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary properties with the factorial speed of growth. However, there are situations where the notion of minimal property is not applicable. A typical example of this type is given by graphs of large girth. It is known that for each particular value of k, the graphs of girth at least k have unbounded tree-, clique- or rank-width, their speed of growth is superfactorial and many algorithmic problems remain NP-hard for these graphs, while the “limit” property of this sequence (i.e., acyclic graphs) has bounded tree-, clique- and rank-width, its speed of growth is factorial, and most of algorithmic problems can be solved in polynomial time in this class. The notion of boundary properties of graphs allows to overcome this difficulty. In this talk we survey some available results on this topic and identify the first boundary class for the Hamiltonian cycle problem.

Joint work with N. Korpelainen and A. Tiskin

Turán's theorem shows that every n-vertex graph with minimum degree n/2 contains a triangle. A proof (for large n) of the Pósa conjecture shows that every n-vertex graph with minimum degree 2n/3 contains the square of a Hamilton cycle; this is a cyclic ordering of the vertices in which every three consecutive vertices forms a triangle. We fill in the gap between these theorems, giving the correct relationship (for large n) between the minimum degree of an n-vertex graph and the lengths of squared cycles which are forced to exist in the graph. We also discuss generalisations of all three theorems to other graphs with chromatic number three, and offer some conjectures on higher chromatic numbers. This is joint work with Julia Böttcher and Jan Hladký.

We discuss recent work on graphical degree sequences, i.e., sequences of integers that correspond to the degrees of the vertices of a graph. Historically, such degree sequences have been used to provide sufficient conditions for graphs to have a certain property, such as being k-connected or hamiltonian. For hamiltonicity, this research has culminated in a beautiful theorem due to Chvátal (1972). This theorem gives a sufficient condition for a graphical degree sequence to be forcibly hamiltonian, i.e., such that every graph with this degree sequence is hamiltonian. Moreover, the theorem is the strongest of an entire class of theorems in the following sense: if the theorem does not guarantee that a sequence π is forcibly hamiltonian, then there exists a nonhamiltonian graph with a degree sequence that majorizes π. Very recently, Kriesell solved an open problem due to Bauer et al. by establishing similar conditions for k-edge connectivity for any fixed k. We will introduce a general framework for such conditions and discuss recent progress and open problems on similar sufficient conditions for a variety of graph properties. This is based on joint work with Bauer, van den Heuvel, Kahl, and Schmeichel.

Min-Max function appear in various contexts in mathematics, computer science, and engineering. For instance, in the analysis of zero-sum two-player games on graphs, Min-Max functions arise as dynamic programming operators. They also play a role in the performance analysis of certain discrete event systems, which are used to model computer networks and manufacturing systems. In each of these fields it is important to understand the long-term iterative behaviour of Min-Max functions. In this talk I will explain how this problem is related to certain combinatorial geometric problems and discuss some results and a conjecture.

We consider finite and simple graphs. We say that a graph G contains a graph F, if F is isomorphic to an induced subgraph of G. A graph G is F-free if it does not contain F. Let ℱ be a (possibly infinite) family of graphs. A graph G is ℱ-free if it is F-free, for every F ∈ ℱ.

Many interesting classes of graphs can be characterized as being ℱ-free for some family ℱ. The most famous such example is the class of perfect graphs. A graph G is perfect if for every induced subgraph H of G, χ(H) = ω(H), where χ(H) denotes the chromatic number of H and ω(H) denotes the size of a largest clique in H. The famous Strong Perfect Graph Theorem states that a graph is perfect if and only if it does not contain an odd hole nor an odd antihole (where a hole is a chordless cycle of length at least four).

In the last 15 years a number of other classes of graphs defined by excluding a family of induced subgraphs have been studied, perhaps originally motivated by the study of perfect graphs. The kinds of questions this line of research was focused on were whether excluding induced subgraphs affects the global structure of the particular class in a way that can be exploited for putting bounds on parameters such as χ and ω, constructing optimization algorithms (problems such as finding the size of a largest clique or a minimum coloring), recognition algorithms and explicit construction of all graphs belonging to the particular class. A number of these questions were answered by obtaining a structural characterization of a class through their decomposition (as was the case with the proof of the Strong Perfect Graph Theorem).

In this talk we survey some of the most recent uses of the decomposition theory in the study of classes of even-hole-free graphs. Even-hole-free graphs are related to β-perfect graphs in a similar way in which odd-hole-free graphs are related to perfect graphs. β-Perfect graphs are a particular class of graphs that can be polynomially colored, by coloring greedily on a particular, easily constructable, ordering of vertices.

In a combinatorial exchange the goal is to find a feasible trade between potential buyers and sellers requesting and offering bundles of indivisible goods. We investigate the approximability of several optimization objectves in this setting and show that the problems of surplus and trade volume maximization are inapproximable even with free disposal and even if each agent's bundle is of size at most 3. In light of the negative results for surplus maximization we consider the complementary goal of social cost minimization and present tight approximation results for this scenario. Considering the more general supply chain problem, in which each agent can be a seller and buyer simultaneously, we prove that social cost minimization remains inapproximable even with bundles of size 3, yet becomes polynomial time solvable for agents trading bundles of size 1 or 2. This yields a complete characterization of the approximability of supply chain and combinatorial exchange problems based on the size of traded bundles. We finally briefly address the problem of exchanges in strategic settings.

This is joint work with Moshe Babaioff and Patrick Briest.

A uniform random intersection graph G(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks. Such graphs arise in particular when modelling the network graph of the well known key predistribution technique due to Eschenauer and Gligor. In this talk we consider the threshold for connectivity and the appearance of a giant component of the graph G(n,m,k) when n → ∞ with k a function of n such that k≥2 and m=⌊n^α⌋ for some fixed positive real number α.

We discuss the following scheduling problem. A two-machine flowshop produces identical parts. Each of the parts is assumed to require a number of manufacturing operations, and the machines are assumed to be flexible enough to perform different operations. Due to economical or technological constraints, some specific operations are preassigned to one of the machines. The remaining operations, called flexible operations, can be performed on either one of the machines, so that the same flexible operation can be performed on different machines for different parts. The problem is to determine the assignment of the flexible operations to the machines for each part, with the objective of maximizing the throughput rate. We consider various cases depending on the number of parts to be produced and the capacity of the buffer between the machines. Along the way, we underline the fact that this problem belongs to the class of "high multiplicity scheduling problem": for this class of problems, the input data can be described in a very compact way due to the fact that the jobs fall into a small number of distinct job types, where all the jobs of a same type possess the same attribute values. High multiplicity scheduling problems have been recently investigated by several researchers who have observed that the complexity of such problems must be analyzed with special care.

Joint work with Hakan Gültekin.

In this talk I will consider computational problems that (A) can be solved in polynomial time for graphs of bounded treewidth and (B) where the order of the polynomial time bound is expected to depend on the treewidth of the instance. Among the considered problems are coloring problems, factor problems, orientation problems and satisfiability problems. I will present an algorithmic meta-theorem (an extension of Courcelle's Theorem) that provides a convenient way for establishing (A) for some of the considered problems and I will explain how concepts from parameterized complexity theory can be used to establish (B).

The connectivity of a communications network can sometimes be enhanced if the nodes are able, at some expense, to form links using an external network. Using graphs, the following is a possible way to model such situations.

Let G = (V,E) be a graph. A subset X of vertices in V may be chosen, the so-called external vertices. An internal path is a normal path in G; an external path is a pair of internal paths P₁ = v₁ · · · v_s, P₂ = w₁ · · · w_t in G such that v_s and w₁ are from the chosen set X of external vertices. (The idea is that v₁ can communicate with w_t along this path using an external link from v_s to w₁.) For digraphs we use similar vocabulary, but then using directed paths.

Next suppose a certain desired connectivity for the network is prescribed in terms of edge, vertex or arc-connectivity. Say that for a given k there need to be at least k edge- (or vertex- or arc-) disjoint paths (which can be internal or external) between any pair of vertices. What is the smallest set X of external vertices such that this can be achieved?

A related problem is the Source Location Problem : In this we need to find, given a graph or digraph and a required connectivity requirement, a subset S of the vertices such that from each vertex in the graph there are at least the required number of edge- (or vertex- or arc-) disjoint paths between any vertex and the set S. And again, the goal is to minimise the number of vertices in S.

It seems clear that the External Network Problem and the Source Location Problem are closely related. In this talk we discuss these relations, and also show some instances where the problems behave quite differently. Some recent results on the complexity of the different types of problems will be presented as well.

Joint work with Matthew Johnson (University of Durham)

We consider graphs whose edges are painted with two colours (some edges might get both colours), and ask, given a fixed such graph H, how large another such graph G can be if it has many vertices but doesn't contain a copy of H. The notion of largeness here is the total weight of G if red edges are given weight p and blue edges weight q, with p+q=1.

This question arises in the applications of Szemerédi's Regularity Lemma, in particular to Ramsey-type games, and to the study of edit distance and property testing.

We shall describe an approach to answering this question and to settling some outstanding issues concerning edit distance.

In this talk, we discuss scheduling and rescheduling problems with controllable job processing times. We start with the optimal allocation of a set of jobs on a set of parallel machines with given machining time capacities. Each job may have different processing times and different convex compression costs on different machines. We consider finding the optimal machine-job allocation and compression level decisions for the total cost. We propose a strengthened conic quadratic formulation for this problem. We provide theoretical and computational results that prove the quality of the proposed reformulation. We next shortly discuss match-up scheduling approach in the same scheduling environment with an initial schedule subject to a machine breakdown. We show how processing time controllability provides flexibility in rescheduling decisions.

We present an O(mn)-time algorithm for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP), where n is the number of vertices (or states) and m is the number of edges (or actions). This improves a recent O(mn^2)-time algorithm of Andersson and Vorobyov.

Joint work with Omid Madani and Mikkel Thorup.

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ by a factor of at most two.

The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that the problems Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity: the former is NP-complete, the latter is solvable in polynomial time. Additionally, our technique enables combinatorial characterisations of clique- and NLC-width that avoid the usual operations on labelled graphs.

The random geometric graph G(n,r) is constructed by picking n vertices X₁, · · · , X_n ∈ [0,1] ^d i.i.d. uniformly at random and adding an edge (X_i, X_j) if ‖X₁-X₂‖ < r. I will discuss the behaviour of the chromatic number of G(n,r) and some related random variables when n tends to infinity and r=r(n) is allowed to vary with n.

In this talk, we first give an overview of several exact approaches to graph colouring: known integer linear programming formulations, approaches based on SDP relaxations, as well as selected approaches not using any mathematical programming. Second, we introduce an integer programming formulation of graph colouring based on reversible clique partition or, seen another way, optimal polynomial-time transformation of graph colouring to multicolouring. The talk will be concluded by discussion of some specifics of applications of graph colouring in timetabling applications and utility of the proposed formulation in this context.

Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, we formalize the setting of Ongoing Markets, by contrast with the classic market scenario, which we term One-Time Markets. The Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. As such, it appears to be a more plausible model of actual markets.

For both market settings, we define and analyze variants of a simple tatonnement algorithm that differs from previous algorithms that have been subject to asymptotic analysis in three significant respects: the price update for a good depends only on the price, demand, and supply for that good, and on no other information; the price update for each good occurs distributively and asynchronously; the algorithms work (and the analyses hold) from an arbitrary starting point. We show that this update rule leads to fast convergence toward equilibrium prices in a broad class of markets that satisfy the weak gross substitutes property.

Our analysis identifies three parameters characterizing the markets, which govern the rate of convergence of our protocols. These parameters are, broadly speaking:

• A bound on the fractional rate of change of demand for each good with respect to fractional changes in its price.
• A bound on the fractional rate of change of demand for each good with respect to fractional changes in wealth.
• The closeness of the market to a Fisher market (a market with buyers starting with money alone).

Joint work with Lisa Fleischer.

The multi-armed bandit paradigm has been studied extensively for over 50 years in Operations Research, Economics and Computer Science literature, modeling online decisions under uncertainty in a setting in which an agent simultaneously attempts to acquire new knowledge and to optimize its decisions based on the existing knowledge. In this talk I'll discuss several new results motivated by web applications, such as content matching (matching advertising to page contest and user's profile) and efficient web crawling.

We discuss control strategies for communication networks such as the Internet or wireless multihop networks, where the aim is to optimize network performance. We describe how welfare maximization can be used as a paradigm for network resource allocation, and can also be used to derive rate-control algorithms. We apply this to the case of multipath data transfers. We show that welfare maximization requires active balancing across paths by data sources, which can be done provided the underlying "network layer" is able to expose the marginal congestion cost of network paths to the "transport layer". When users are allowed to change the set of paths they use, we show that for large systems the path-set choices correspond to Nash equilibria, and give conditions under which the resultant Nash equilibria correspond to welfare maximising states. Moreover, simple path selection policies that shift to paths with higher net benefit can find these states.

We conclude by commenting on incentives, pricing and open problems.

Most data networks nowadays employ shortest path routing protocols to control the flow of data packets. With these protocols, all end-to-end traffic streams are routed along shortest paths with respect to some administrative routing weights. Dimensioning and routing planning are extremely difficult for such networks, because end-to-end routing paths cannot be configured individually but only jointly and indirectly via the routing weights. Additional difficulties arise if the communication demands must be sent unsplit through the network - a requirement that is often imposed to ensure tractability of end-to-end traffic flows and to prevent package reordering in practice. In this case, the lengths must be chosen such that the shortest paths are uniquely determined for all communication demands.

In this talk we consider the minimum congestion unsplittable shortest path routing problem MinConUSPR: Given a capacitated digraph D = (V, A) and traffic demands d_(s,t), (s, t) ∈ K ⊆ V², the task is to find routing weights λ_a ∈ ℤ₊, a ∈ A, such that the shortest (s, t)-path is unique for each (s, t) ∈ K and the maximum arc congestion (induced flow/capacity ratio) is minimal.

We discuss the approximability of this problem and the relation between the unsplittable shortest path routing paradigm and other routing schemes. We show that MinConUSPR is NP-hard to approximate within a factor of O(|V|^1-ε), but approximable within min(|A|, |K|) in general. For the special cases where the underlying graph is an undirected cycle or a bidirected ring, we present constant factor approximation algorithms. We also construct problem instances where the minimum congestion that can be obtained by unsplittable shortest path routing is a factor of Ω(|V|²) larger than that achievable by unsplittable flow routing or shortest multi-path routing, and a factor of Ω(|V|) larger than that achievable by unsplittable source-invariant routing.

I will consider waves in finite domains, for example water waves in a swimming pool. For such waves to exchange energy among different modes, these modes must be in resonance in both frequency and wavenumber, which leads to a set of nontrivial conditions/equations in integers. I will discuss some known results and open questions about the solutions of these Diophantine equations.

The observation that many natural and engineered networks exhibit scale-free degree distributions, and that such networks are particularly prone to epidemic outbreaks, raises questions about how best to control epidemic spread on such networks.

We will begin with some background on threshold phenomena for epidemics, describing how the minimum infection rate needed to sustain long-lived epidemics is related to the cure rate and the topology of the graph. In particular, we will see that, on scale-free networks, this minimum infection rate tends to zero as the network grows large. We will describe two ways of tackling this problem. One involves allocating curing or monitoring resources non-uniformly, favouring high-degree nodes. Another mechanism, called contact tracing, involves identifying and curing neighbours (or contacts) of infected nodes, and is used in practice. We will present some mathematical results for both these mechanisms.

Joint work with Borgs, Chayes, Saberi and Wilson.

The index of a Nash equilibrium is an integer that is related to notions of ``stability'' of the equilibrium, for example under dynamics that have equilibria as rest points. The index is a relatively complicated topological notion, essentially a geometric orientation of the equilibrium. We prove the following theorem, first conjectured by Hofbauer (2003), which characterizes the index in much simpler strategic terms:

Theorem. A generic bimatrix game has index +1 if and only if it can be made the unique equilibrium of an extended game with additional strategies of one player. In an mxn game, it suffices to add 3m strategies of the column player.

The main tool to prove this theorem is a novel geometric-combinatorial method that we call the "dual construction," which we think is of interest of its own. It allows to visualize all equilibria of an mxn game in a diagram of dimension m-1. For example, all equilibria of a 3xn game are visualized with a diagram (essentially, of suitably connected n+3 points) in the plane. This should provide new insights into the geometry of Nash equilibria.

Joint work with Arndt von Schemde.

In view of the apparent computational difficulty of computing a Nash equilibrium of a game, recent work has addressed the computation of "approximate Nash equilibrium". The standard criterion of "no incentive for any player to change his strategy" is here replaced by "small incentive for any player to change his strategy". The question is, how small an incentive can we aim for, before once again we have a computationally difficult problem? In this talk, I explain in detail what is meant by Nash equilibrium and approximate Nash equilibrium, and give an overview of some recent results.

In the classic minimum makespan scheduling problem, we are given an input sequence of jobs with processing times. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. We consider online scheduling algorithms without preemption. Much effort has been made to narrow the gap between upper and lower bounds on the competitive ratio of this problem.

A quite good and easy approximation can be achieved by sorting the jobs according to their size and than assigning them greedily to machines. However, the complete sorting of the input sequence contradicts the notion of an online algorithm. Therefore, we propose a new method to somewhat reorder the input in an online manner. Although our proofs are technically surprisingly simple, we give, for any number of identical machines, tight and significantly improved bounds on the competitive ratio for this new method.

This talk is based on joint work with Deniz Özmen and Matthias Westermann

We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit-demand bidders. We show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant times the revenue of the best fixed price scheme.

This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained air. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

Joint work with Anna Karlin, Mohammad Mahdian, and Kunal Talwar

We will consider generating a random vertex colouring of a graph using a Markov chain. The aim is to determine the smallest number of colours, measured as a multiple of the maximum degree, for which the chain converges in time polynomial in the number of vertices. We will examine this problem for the case of an Erdős-Rényi random graph. This has been studied previously for graphs with small edge density. However, the methods used in the sparse case do not seem applicable as the edge density becomes larger. We will describe a different approach, which can be used to obtain results for denser graphs.

We suggest a game theoretic framework (so called now 'interval model') for the analysis of option prices in financial mathematics. This leads to remarkable explicit formulas and effective numeric procedures for rainbow (or coloured) options hedging.

How efficiently can one move about in a network linking a configuration of n cities? Here the notion of "efficient" has to balance (a) total network length against (b) short network distances between cities. My talk will explain how to use Poisson line processes to produce networks which are nearly of shortest total length, which make the average inter-city distance almost Euclidean.

This is joint work with David Aldous.

We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite point set P, our goal is to find a set C of size k such that the sum of errors D(P,C) = Σ_{{p in P}} min_{{c in C}} {D(p,c)} is minimized. The main result in this talk can be stated as follows: There exists an O(n 2^{(k/ε)^O(1)}) time (1+ε)-approximation algorithm for the k-median problem with respect to D, if the 1-median problem can be approximated within a factor of (1+ε) by taking a random sample of constant size and solving the 1-median problem on the sample exactly.

Using this characterization we obtain the first linear time (1+ε)-approximation algorithms for the k-median problem for doubling metrics, for the Kullback-Leibler divergence, Mahalanobis distances and some special cases of Bregman divergences.

We consider the notorious travelling salesman problem (TSP) and such seemingly well-studied algorithms as the Held & Karp dynamic programming algorithm, the double-tree and Christofides heuristics, as well as algorithms for finding optimal pyramidal tours. We show how the ideas from these classical algorithms can be combined to obtain one of the best tour-constructing TSP heuristics. The main message of our presentation: despite the fact that the TSP has been investigated for decades, and thousands(!) of papers have been published on the topic, there are still plenty of exciting open problems, some of which (we strongly believe) are not that difficult to resolve.

We consider the notorious travelling salesman problem (TSP) and such seemingly well-studied algorithms as the Held & Karp dynamic programming algorithm, the double-tree and Christofides heuristics, as well as algorithms for finding optimal pyramidal tours. We show how the ideas from these classical algorithms can be combined to obtain one of the best tour-constructing TSP heuristics. The main message of our presentation: despite the fact that the TSP has been investigated for decades, and thousands(!) of papers have been published on the topic, there are still plenty of exciting open problems, some of which (we strongly believe) are not that difficult to resolve.

Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or ½, such cuts are known as {0,½}-cuts. This talk reports on our study to separate general {0,½}-cuts effectively, despite its NP-completeness.

We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated {0,½}-cut, we formulate the (reduced) problem as an integer linear program. Some simple heuristic separation routines complete the algorithmic framework.

Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.

Koller, Megiddo and von Stengel showed in 1994 how to efficiently find minimax behavior strategies of two-player imperfect information zero-sum extensive games using linear programming. Their algorithm has been widely used by the AI-community to solve very large games, in particular variants of poker. However, it is a well known fact of game theory that the Nash equilibrium concept has serious deficiencies as a prescriptive solution concept, even for the case of zero-sum games where Nash equilibria are simply pairs of minimax strategies. That these deficiencies show up in practice in the AI-applications was documented by Koller and Pfeffer. In this talk, we argue that the theory of equilibrium refinements of game theory provides a satisfactory framework for repairing the deficiencies, also for the AI-applications. We describe a variant of the Koller, Megiddo and von Stengel algorithm that computes a *quasi-perfect* equilibrium and another variant that computes all *normal-form proper* equilibria. Also, we present a simple yet non-trivial characterization of the normal form proper equilibria of a two-player zero-sum game with perfect information.

The talk is based on joint papers with Troels Bjerre Sørensen, appearing at SODA'06 and SODA'08.

This talk examines the computational complexity of approximating the number of solutions to a Boolean constraint satisfaction problem (CSP). It extends a line of investigation started in a classical paper of Schaefer on the complexity of the decision problem for CSPs, and continued by Creignou and Hermann, who addressed exact counting.

We find that the class of Boolean CSPs exhibits a trichotomy. Depending on the set of allowed relations, the CSP may be polynomial-time solvable (even exactly); or the number of solutions may be as hard to approximate as the number of accepting computations of a non-deterministic Turing machine. But there is a third possibility: approximating the number of solutions may be complete for a certain logically defined complexity class, and hence equivalent in complexity to a number of natural approximate counting problems, of which independent sets in a bipartite graph is an example.

All the necessary background material on approximate counting and CSPs will be covered.

This is joint work with Martin Dyer (Leeds) and Leslie Ann Goldberg (Liverpool).

From the theory of graph minors we know that the class of planar graphs is the only critical class with respect to tree-width. In this talk, we reveal a critical class with respect to clique-width, a notion generalizing tree-width. This class is known in the literature under different names, such as unit interval, proper interval or indifference graphs, and has important applications in various fields. We prove that the unit interval graphs constitute a minimal hereditary class of unbounded clique-width and discuss some applications of the obtained result.

In this talk we study basic network design problems with modular capacity assignment. The focus is on classes of strong valid inequalities that are defined for cuts of the underlying network. We show that regardless of the link model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Accordingly, we focus on the facial structure of the cutset polyhedra. A large class of facets of cutset polyhedra is defined by flow-cutset inequalities. These inequalities are presented in a unifying way for different model variants. We propose a generic separation algorithm and in an extensive computational study on 54 instances from the survivable network design library (SNDlib), we show that the performance of CPLEX can significantly be enhanced by this class of cutting planes.

Suppose we have a grid mxn, two real-valued functions f and g on [m] and [n] respectively, and a threshold value b. We declare a point (i,j) in the grid to be open if f(i) + g(j) is at most b. It turns out that, if there is a path of open points from the bottom point (1,1) to the top point (m,n), then there is a monotone path of open points, i.e., if we can get from bottom to top at all, then we can do so without having to retreat.

This is an instance of the following much more general result. Let f be a submodular function on a modular lattice L; we show that there is a maximal chain C in L on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of L, in a certain well-behaved partial order -- the "worm order" -- on sequences of reals. One consequence is that the maximum value of f on C is minimised over all such paths. We discuss the worm order, relate our work to that on searching a graph, and mention some sample applications.

Joint work with Peter Winkler.

In this talk I will first present the basic working principles of Ant Colony Optimization (ACO) and then explain some of our work on applying ACO to vehicle routing problems. The main idea in this context is to exploit problem knowledge to improve the performance of the general purpose heuristic ACO.

We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family L that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in L. We also prove the following combinatorial result which can be viewed as a generalization of many results for a "spanning tree with many leaves" in the undirected case, and which is interesting on its own: If a digraph D ∈ L of order n with minimum in-degree at least 3 contains a rooted spanning tree, then D contains one with at least (n/4)^1/3-1 leaves.

Joint work with Noga Alon, Fedor Fomin, Michael Krivelevich and Saket Saurabh

An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratios w.r.t. the congestion in the network (i.e., maximum load of a network link).

In this talk I will present a new hierarchical decomposition technique that leads to good oblivious routing algorithms. This decomposition can also be used as a generic tool for solving a large variety of cut based problems in undirected graphs.

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^1/3, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^1/3 is best possible, resolving the long-standing overhang problem up to a constant factor.

I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.

High performance floating point hardware is notoriously difficult to design correctly. In fact, until recently, the most expensive hardware bug encountered in industry, was the Intel FDIV bug in 1994 that lead to a charge of 450 million dollars against earnings. At the same time, floating point arithmetic is unique in that there is a fairly unambiguous specification, the IEEE 754 standard, which all implementations should obey. Unfortunately, bridging the gap between the mathematical specification of the standard and a low-level implementation is an extremely difficult task. At Intel we have developed an approach that combines the strengths of theorem proving with symbolic trajectory evaluation (a type of model checking), that allows us to completely verify the correctness of todayÇs floating point units. In this talk I will discuss the evolution of this approach and discuss some of the results that have been obtained in addition to areas of future research.

It is well known that boundedness of tree-width implies polynomial-time solvability of many algorithmic graph problems. The converse statement is generally not true, i.e., polynomial-time solvability does not necessarily imply boundedness of tree-width. However, in graphs of bounded vertex degree, for some problems, the two concepts behave in a more consistent way. We study this phenomenon with respect to three important graph problems -- dominating set, independent dominating set and induced matching -- and obtain several results toward revealing the equivalency between boundedness of the tree-width and polynomial-time solvability of these problems in bounded degree graphs. Joint work with Martin Milanic.

The PCP theorem [AS, ALMSS] specifies a way of encoding any mathematical proof such that the validity of the proof can be verified probabilistically by querying the proof only at a constant number of locations. Furthermore, this encoding is complete and sound, i.e., valid proofs are always accepted while invalid proofs are accepted with probability at most 1/2. A natural question that arises in the construction of PCPs is by how much does this encoding blow up the original proof while retaining low query complexity.

The study of efficient probabilistic checkable proofs was initiated in the works of Babai et. al. [BFLS] and Feige at. al. [FGLSS] with very different motivation and emphases. The work of Babai et. al. considered the direct motivation of verifying proofs highly efficiently. In contrast, Feige et. al. established a dramatic connection between efficient probabilistically checkable proofs (PCPs) and the inapproximability of optimization problems.

In this talk, I'll review some of the recent works of Ben-Sasson et. al. [BGHSV'04, BGHSV'05], Dinur-Reingold [DR], Ben-Sasson and Sudan [BS'04] and Dinur [Din'06] that have led to the construction of PCPs that are at most a polylogarithmic factor longer than the original proof and furthermore, are checkable by a verifier running in time at most polylogarithmic in the length of the original proof.

An important ingredient in these constructions is a a new variant of PCPs called "PCPs of Proximity''. These new PCPs facilitate proof composition, a crucial component in PCP construction. I'll outline how these new PCPs allow for shorter PCP constructions and efficient proof verification

We give an overview of the optimization challenges addressed in recent years ranging from frequency assignment in mobile networks to multi-layer network design in backbone networks. We discuss the practical problems, the mathematical modelling, the methodologies used to tackle these problems, and the results achieved.