We will discuss lower and upper bounds for the size of k-AP-free subsets of Z_mⁿ, that is, for r_k(Z_mⁿ), in certain cases. Specifically, we will look at some recent lower bounds given by Elsholtz and myself. In the case m=4,k=3 we present a construction which gives the tight answer up to n ≤ 5, and point out some connection with coding theory.

Compared to the highly successful flat clustering (e.g. k-means), despite its important role and applications in data analysis, hierarchical clustering has been lacking in rigorous algorithmic studies until late due to absence of rigorous objectives. Since 2016, a sequence of works has emerged and gave novel algorithms for this problem in the general metric setting. This was enabled by a breakthrough by Dasgupta, who introduced a formal objective into the study of hierarchical clustering.

In this talk I will give an overview of our recent progress on models and scalable algorithms for hierarchical clustering applicable specifically to high-dimensional vector data. I will first discuss various linkage-based algorithms (single-linkage, average-linkage) and their formal properties with respect to various objectives. I will then introduce a new projection-based approximation algorithm for vector data. The talk will be self-contained and doesn’t assume prior knowledge of clustering methods.

Based on joint works with Vadapalli (ICML’18) and Charikar, Chatziafratis and Niazadeh (AISTATS’19)

Ryser conjectured that the vertices of every r-edge-coloured graph with independence number i can be covered be (r - 1)i monochromatic trees. Motivated by a problem in analysis, Milicevic recently conjectured that moreover one can ensure that these trees have bounded diameter. We'll show that the two conjectures are equivalent. As a corollary one obtains new results about Milicevic's Conjecture.

This is joint work with Abu Khazneh.

We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allows us to capture the progress the random walk makes through t-step probabilities.

We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n^2), generalising a well-known result for static graphs.

Joint Work with Luca Zanetti

https://arxiv.org/abs/1903.01342

In this talk I will give an introduction to Design Theory from the combinatorial perspective of (hyper)graph decompositions. I will survey some recent progress on the existence of decompositions, with particular attention to triangle decompositions of graphs, which provide a simple (yet still interesting) illustration of more general results.

A classical theorem of Kuratowski characterises graphs embeddable in the plane by two obstructions. More precisely, a graph is planar if and only if it does not contain the complete graph K_5 or the complete bipartite graph K_{3,3} as a minor.

Can you characterise embeddability of 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski’s characterisation of graph planarity?

Coding theory is a central tool in communication, cryptography, algorithms, complexity, and more. Loosely speaking, codes are mathematical objects that provide means to endow information with structure that admits robustness to noise.

In recent years, there has been a surge of interest in highly structured codes that exhibit local-to-global phenomena. Such codes admit various types of algorithms that make their decisions based on a small local view, and thus run in sublinear time. In this talk, I will present recent results regarding two fundamental types of codes with a local-to-global structure: locally decodable codes and locally testable codes. In addition, I will discuss several applications of such codes to theoretical computer science and discrete mathematics, as well as discuss old open problems and new approaches for resolving them.

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs. The results apply, for example, to random bipartite Δ-regular graphs, for which no efficient algorithms were known in the non-uniqueness regime of the infinite Δ-regular tree. Joint work with Peter Keevash and Will Perkins.

Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the many applications to Internet advertisement and to the sharing economy.

In two-sided markets, both buyers and sellers act strategically. An ideal goal in two-sided markets is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and budget-balanced mechanisms (BB), which requires that the mechanism does not subsidize the market or make an arbitrary profit from the exchange. Unfortunately, Myerson and Satterthwaite proved in 1983 that this goal cannot be achieved even in the bayesian setting and for the simple case of only one buyer and one seller.

In this talk, I’ll discuss meaningful trade-offs and algorithmic approximations of the above requirements by presenting several recent results and some challenging open problems.

Petri nets, also known as vector addition systems, are a long established and widely used model of concurrent processes. The complexity of their reachability problem is one of the most prominent open questions in the theory of verification. That the reachability problem is decidable was established by Mayr in his seminal STOC 1981 work, and the currently best upper bound is non-primitive recursive cubic-Ackermannian of Leroux and Schmitz from LICS 2015. We show that the reachability problem is not elementary. Until this work, the best lower bound has been exponential space, due to Lipton in 1976.

Joint work with Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic and Jerome Leroux.

We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) \lambda > 0. For constant \Delta, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree \Delta when \lambda < \lambda_c(\Delta). Sly (2010) showed that there is no FPRAS, unless NP=RP, when \lambda > lambda_c(\Delta). The threshold \lambda_c(\Delta) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite \Delta-regular tree. The running time of Weitz's algorithm is exponential in log(\Delta).

Here we present an FPRAS for the partition function whose running time is O*(n^2). We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant \Delta_0 such that for all graphs with maximum degree \Delta \ge \Delta_0 and girth > 6 (i.e., no cycles of length at most 6), the mixing time of the Glauber dynamics is O(n log(n)) when \lambda < \lambda_c(\Delta). Our work complements that of Weitz which applies for small constant \Delta whereas our work applies for all \Delta at least a sufficiently large constant \Delta_0 (this includes \Delta depending on n=|V).

Our proof utilises loopy BP (belief propagation) which is a widely-used algorithm for inference in graphical models. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics, after a short burn-in period, converges close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth > 5 and \lambda < \lambda_c(\Delta).

This is a joint work with Tom Hayes, Daniel Stefankovic, Eric Vigoda and Yitong Yin.

In order to avoid agonisingly slow query response times over very large sets of data, two strategies are employed. One strategy is to reduce the response time by optimising the query execution for the underlying data. The other strategy is to provide approximate answers in the meantime. Both strategies rely on data summaries that can estimate the number of points along box-shaped ranges. In the literature many summaries have been proposed, ranging from ones offering formal guarantees to heuristics geared towards practical performance. In my talk I will primarily focus on summaries providing tight bounds for the estimation error, discuss prominent approaches and present results from a joint work with Anton Dignös and Johann Gamper. In addition to that, I will discuss open problems and challenges involved in formalising the problem without risking to lose touch with practical applications.

Linial and Morgenstern conjectured that, among all tournaments with a given density d of cycles of length three, the density of cycles of length four is minimized by a random blow-up of a transitive tournament with all but one parts of equal sizes, i.e., the structure of extremal tournaments resembles the one that appears in the famous Erdos-Rademacher problem concerning the minimum density of triangles in a graph with a given edge density. We prove the conjecture for d>=1/36 and demonstrate that the structure of extremal examples is more complex than expected and give its full description for d>=1/16. Contrary to many recent results in this area, our proof is not based on the flag algebra method but it uses methods from spectral graph theory. At the end of the talk, we consider a related problem of determining the maximum number of cycles of length k in a tournament and solve this problem when k=8 or k is not divisible by four.

This talk contains results obtained jointly with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz, Jonathan Noel and Jan Volec.

Many modern computing systems are distributed and built in a decentralized way on top of large networks. As one of the key challenges when running a distributed algorithm in a large network, typically no node can know the state of the whole network and each node thus each node has to base its decisions on only partial, mostly local information about the network. The major goal of the research on local distributed algorithms is to understand to what extent nodes in a network can achieve a global goal such as solving some graph problem, based on only local information.

In my talk, I will focus on the role of using randomization in local distributed graph algorithms. In many cases, there currently is a large gap between the best randomized and deterministic algorithms and understanding whether this gap is inherent, is considered to be one of the central open questions of the area. I will discuss recent results that shed some light on what randomness is really needed for and that also allow to identify simple and basic problems that are complete for the class of problems that have efficient randomized distributed algorithms and for which we do not know efficient deterministic algorithms.

The deck of a graph G is given by the multiset {G-v:v in V(G)} of (unlabelled) subgraphs, which are called cards. The graph reconstruction conjecture states that no two non-isomorphic graphs (on at least three vertices) can have the same deck. The number of edges of a graph can be computed from its deck and Brown and Fenner show that the size of G can be reconstructed as well after any 2 cards have been removed from the deck (for n≤ 29). We show that for sufficiently large n, the number of edges can be computed whenever at most 20/√ n cards are missing. I will talk about the background of the problem, the main ideas of the proof and my favourite open problems in the area.

Joint work with Hannah Guggiari and Alex Scott.

We study the complexity of problems in PPAD ∩ PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a contraction map, finding the unique sink of a Unique Sink Orientation (USO), and solving the P-matrix Linear Complementarity Problem (P-LCP). Each of these are promise-problems, and when the promise holds, they always possess unique solutions.

We define the complexity class UEOPL to capture problems of this type. We show that UEOPL ⊆ CLS, and that all of our motivating problems are contained in UEOPL: specifically USO, P-LCP, and finding a fixpoint of a Piecewise-Linear Contraction under an ℓp-norm all lie in UEOPL. Our results also imply that parity games, mean-payoff games, discounted games, and simple-stochastic games lie in UEOPL.

All of our containment results are proved via a reduction to a problem that we call One-Permutation Discrete Contraction (OPDC). This problem is motivated by a discretized version of contraction, but it is also closely related to the USO problem. We show that OPDC lies in UEOPL, and we are also able to show that OPDC is UEOPL-complete.

Based on joint work with Spencer Gordon, Ruta Mehta, and Rahul Savani.

In this talk, we prove a scaling limit for the size of the largest components of a critical random intersection graph in which each individual is assigned to each community with a uniform probability p, all independently of each other. We show that the order of magnitude of the largest component depends significantly on the asymptotic behaviour of the ratio between the number of individuals and communities. We further discuss how this result relates to the known scaling limits of critical inhomogeneous random graphs.

A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon in not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario.

A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon T, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.

In the file migration problem, we are given a metric space (X,d) and an indivisible file of size D needs to be stored in one of the points X. At each time step, a request arrives from some point r in X, incurring a cost of d(r,x), where x is the point where the file is stored. We can then move the file to a new point y, paying D d(x,y). This problem has been studied in the online setting, and the best known competitive ratio has been 4.086 (Bartal et al., SODA 1997). In this talk I will discuss a 4-competitive algorithm. One interesting feature of this result is the extensive use of computers in both designing and analyzing the algorithm.

The development of the field of additive combinatorics in recent years has provided, among other things, a collection of fascinating and deep, elementary tools for estimating the sizes of discrete subsets of abelian groups. Tao in 2010 connected these results with the entropy of discrete probability measures: Interpreting the entropy of a discrete random variable as the logarithm of its "effective support size," he provided a series of new inequalities for the discrete entropy. We will review this background and describe how Tao's results extend in a nontrivial way to the entropy of random elements in general abelian groups. The somewhat surprising key difference between the discrete and the general case is that the "functional submodularity" property of the discrete entropy needs to be replaced by the general "data processing property" of the entropy.

No background in information theory, entropy or additive combinatorics will be assumed.

A beautiful coupling argument by McDiarmid can translate results on the appearance of a spanning (Hamilton) cycle in random graphs to random directed graphs and spanning cycles with different patterns of directions. However, this does not determine the sharp threshold for the appearance for each possible pattern of edges, and, moreover, it cannot determine when a random directed graph is likely to contain a spanning cycle for each possible pattern of directions simultaneously.

I will discuss techniques for finding spanning cycles in random graphs and directed graphs, and McDiarmid's coupling, and how these can be combined to solve these problems.

The termination analysis of linear loops plays a key role in several areas of computer science, including program verification and abstract interpretation. Such deceptively simple questions also relate to a number of deep open problems, such as the decidability of the Skolem and Positivity Problems for linear recurrence sequences, or equivalently reachability questions for discrete-time linear dynamical systems. In this paper, we introduce the class of o-minimal invariants, which is broader than any previously considered, and study the decidability of the existence and algorithmic synthesis of such invariants as certificates of non-termination for linear loops equipped with a large class of halting conditions. We establish two main decidability results, one of them conditional on Schanuel's conjecture in transcendental number theory.

S is an equilateral set in a normed space X, if the distance of any two distinct points of S is 1. The equilateral number e(X) of X is the maximum cardinality of an equilateral set in X. A conjecture of Petty states that e(X)>=n+1 for any X of dimension n. This conjecture is still wide open. We study equilateral sets in subspaces of l_\infty^n of fixed codimension k, and prove exponential lower bounds on their equilateral number. This proves Petty's conjecture for these classes of norms, provided that n is sufficiently large compared to k. In particular, we obtain that if X is an n-dimensional normed space with a centrally symmetric convex polytope of at most 4n/3-o(n) pairs of facets as a unit ball, then e(X)>=n+1. We also prove lower bounds for the equilateral number of norms that are close to subspaces of l_\infty^n.

Good-for-Games (GFG) automata offer a compromise between deterministic and nondeterministic automata. They can resolve non-deterministic choices in a step-by-step fashion, without needing any information about the remaining suffix of the word. These automata can be used to solve games with omega-regular conditions, and in particular were introduced as a tool to solve Church's synthesis problem. GFG automata can offer exponential succinctness compared to the deterministic automata that are classically used in this context.

The problem of recognizing whether a given automaton is GFG is surprisingly challenging, and an efficient solution would be interesting from both theoretical and practical points of view. After introducing GFG automata through motivations and examples, I will detail the most recent advancements on this topic, namely a polynomial-time algorithm for recognizing GFG Büchi automata.

Different types of automata over words and trees offer different trade-offs between expressivity, conciseness, and the complexity of decision procedures. Alternating weak automata enjoy simple algorithms for emptiness and membership checks, which makes transformations into automata of this type particularly interesting. For instance, an algorithm for solving two-player infinite games -- such as parity games -- can be viewed as a special case of such a transformation. However, our understanding of the worst-case size blow-up that these transformations can incur is rather poor.

I will present a quasi-polynomial transformation of alternating parity word automata into alternating weak automata, improving on the existing exponential upper bound.

If time allows, I will also mention that on trees the situation is drastically different: alternating parity tree automata (and even universal co-Buchi tree automata), can be exponentially more concise than alternating weak automata.

This talk is based on "On the way to alternating weak automata", co-authored with Udi Boker, to appear at FSTTCS'18.

The binary deletion channel is a simple point-to-point communications channel in which a stream of bits is sent by a sender and each bit is independently either delivered to the receiver or discarded. Despite its simplicity, determining the Shannon capacity of the channel; i.e., the best possible rate of reliable transmission, remains as one of the most challenging open problems in information theory. The deletion channel has regained great attention in recent years in part due to the significance to DNA storage systems, in addition to its fundamental importance.

We develop a systematic approach, based on convex programming and real analysis, for obtaining upper bounds on the capacity of the binary deletion channel and, more generally, channels with i.i.d. insertions and deletions. Our framework can be applied to obtain capacity upper bounds for any repetition distribution. Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate, real-valued, and concave function over a bounded interval. The corresponding univariate function is carefully designed according to the underlying distribution of repetitions and the choices vary depending on the desired strength of the upper bounds as well as the desired simplicity of the function (e.g., being only efficiently computable versus having an explicit closed-form expression in terms of elementary, or common special, functions).

Among many other results, we show that the capacity of the binary deletion channel with deletion probability d is at most (1-d) log φ for d ≤ 1/2, and, assuming that the capacity function is convex, is at most 1-d log(4/φ) for d < 1/2, where φ is the golden ratio. This is the first nontrivial capacity upper bound for any value of d outside the limiting case d → 0 that is fully explicit and proved without computer assistance.

Based on work appearing in STOC’18 and JACM; pre-print here.

A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this fact, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text’s size by exploiting its repetitiveness. Lempel-Ziv 77 is one of the most successful and well-known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, macro schemes, collage systems, and the compact directed acyclic word graph. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all distinct text’s substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives the approximation ratios of dictionary compressors with respect to the smallest string attractor and allows us to uncover new asymptotic relations between the output sizes of different dictionary compressors. We then show that the k-attractor problem — deciding whether a text has a size-t set of positions capturing all substrings of length at most k — is NP-complete for k≥ 3. This, in particular, includes the full string attractor problem. We provide several approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower and upper bounds for the random access problem on string attractors. The upper bound is proved by showing a data structure supporting queries in optimal time. Our data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, it matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access problem for all these compressors.

This talk is based on joint work with Nicola Prezza that appeared at STOC 2018.

We show that a nonnegative 4-variate homogeneous polynomial (form) f in R[x,y,z,t] of degree 4 is the ratio p/q of forms p, q of degrees 8 and 4, resp., where p, q are sums of squares of forms. This allows an efficient check of nonnegativity of f using semidefinite optimization (SDP). No similar results were known for forms of degree>2 in more than 3 variables. (The 3-variate case was settled in 1893 by Hilbert, and slightly improved upon for small degrees in the past 10 years).

We conjecture that there are "special" f=at²+2bt+c, where a, b,c in R[x,y,z], for which the "8/4"- degree bound is sharp. In particular the ternary sextic h:=Disc(f)=ac-b² cannot be s.o.s., and we construct such h. However, SDPs stipulating that f cannot be written as p/q with smaller than "8/4" degrees resist solving, despite their relatively modest sizes. We discuss related shortcomings of SDP solvers, and a problem of a number-theoretic flavour, of constructing a "sparse" h with small coefficients.

In the online packet scheduling problem with deadlines, the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The goal is to develop an algorithm with the lowest possible competitive ratio, which is the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm.

In this talk, we present a φ-competitive online algorithm (where φ≈1.618 is the golden ratio), matching the previously established lower bound. We then outline main ideas and techniques of its analysis. Finally, we discuss possible extensions of this work.

Joint work with Marek Chrobak, Łukasz Jeż, and Jiří Sgall.

It is known that in a complete graph with independent exponential edge weights the distance between two fixed vertices is asymptotically log n/n. We look at the cost X_k of k-th minimal path between two fixed vertices, defined as the cheapest path in G after having deleted the previous k-1 minimal paths. We show that X_k/(log n/n) tends to 1 for k=o(log n). We also look at variants of the problem and a strengthening for small k. This talk is based on joint work with P. Balister, B. Mezei and G. Sorkin.

We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the state space of WFA. Our development is based on spectral properties of sets of linear operators. In particular, the joint spectral radius of the transition matrices of WFA plays a central role. We also study continuity properties of the bisimulation pseudometric, establish an undecidability result for computing the metric, and give a preliminary account of applications to spectral learning of weighted automata. Finally, we compare our metric to other bisimulation metrics in the special case of probabilistic automata. (https://arxiv.org/abs/1702.08017)

The plan is first to briefly recall the notion of vector addition systems with states (an equivalent to Petri nets) and the known results on complexity of related basic problems; this will be followed by sketching the main ideas of the paper to appear at Petri Nets 2018.

The coverability and boundedness problems are well-known exponential-space complete problems for vector addition systems with states (or Petri nets). The boundedness problem asks if the reachability set (for a given initial configuration) is finite. Here we consider a dual problem, the co-finiteness problem that asks if the complement of the reachability set is finite; by restricting the question we get the co-emptiness (or universality) problem that asks if all configurations are reachable.

We show that both the co-finiteness problem and the co-emptiness problem are complete for exponential space. While the lower bounds are obtained by a straightforward reduction from coverability, getting the upper bounds is more involved; in particular we use the bounds derived for reversible reachability by Leroux in 2013.

Joint work with J. Leroux and G. Sutre.

The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau et al. 2002, Grohe 2003, and Atserias et al. 2007 establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithm (unconditionally) as bounded treewidth modulo homomorphic equivalence.

The general-valued constraint satisfaction problem (VCSP) is a generalisation of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the k-th level of the Sherali-Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognising the tractable cases; the latter has an application in database theory.

Joint work with Clement Carbonnel and Standa Zivny.

The Travelling Salesman Problem (TSP) is the fundamental and one of the most studied combinatorial optimisation problem. Despite several improvements of Christofides's approximation ratio (the graphic TSP) there is still a significant gap between currently the best known approximation ratio and hardness results. Our focus will be on the hardness results where several improvements have been made in the last two decades. Currently the only known method to prove the approximation hardness results for the Graphic TSP is a gap preserving reduction. However, the gap preserving techniques have been improved by constructions of better amplifiers, gadgets and transformations. As a result of that the initial APX-hardness results presented without any explicit constant (Papadimitriou & Yannakakis, 1993) was improved to the current best known value of 123/122 (Lampis at al., 2015).

In this talk we present further improvement of these techniques based on the weighted amplifiers.

This is joint work with Miroslav Chlebik (University of Sussex).

We show that Tao’s spectral proof of the algebraic regularity lemma for certain classes of finite structures has a very natural formulation in the context of graphons. We apply these techniques to study expander difference polynomials over fields with powers of Frobenius.

In this fairly technical talk, I will show that the equivalence problem for copyless cost register automata is undecidable, disproving a conjecture of Alur et. al from 2012. “Cost register automata” simply means automata equipped with nonnegative integer registers where each transition induces an update expressed using increments and minimums; the automaton outputs a specific register on acceptance. Further, “copyless” means that each register is used at most once in the update functions, for each transition. The constructions focus on simulating counter machines with zero-tests: we will see that a copyless cost register automaton can “check” that an input string is a correct execution of a counter machine.

Joint work with S. Almagor, F. Mazowiecki and G. A. Pérez.

Full paper: arXiv:1804.06336

We develop a new family of variance reduced stochastic gradient descent methods for minimizing the average of a very large number of smooth functions. Our method - JacSketch - is motivated by novel developments in randomized numerical linear algebra, and operates by maintaining a stochastic estimate of a Jacobian matrix composed of the gradients of individual functions. In each iteration, JacSketch efficiently updates the Jacobian matrix by first obtaining a random linear measurement of the true Jacobian through (cheap) sketching, and then projecting the previous estimate onto the solution space of a linear matrix equation whose solutions are consistent with the measurement. The Jacobian estimate is then used to compute a variance-reduced unbiased estimator of the gradient, followed by a stochastic gradient descent step. Our strategy is analogous to the way quasi-Newton methods maintain an estimate of the Hessian, and hence our method can be seen as a stochastic quasi-gradient method. Indeed, quasi-Newton methods project the current Hessian estimate onto a solution space of a linear equation consistent with a certain linear (but non-random) measurement of the true Hessian. Our method can also be seen as stochastic gradient descent applied to a controlled stochastic optimization reformulation of the original problem, where the control comes from the Jacobian estimates.

We prove that for smooth and strongly convex functions, JacSketch converges linearly with a meaningful rate dictated by a single convergence theorem which applies to general sketches. We also provide a refined convergence theorem which applies to a smaller class of sketches, featuring a novel proof technique based on a stochastic Lyapunov function. This enables us to obtain sharper complexity results for variants of JacSketch with importance sampling. By specializing our general approach to specific sketching strategies, JacSketch reduces to the celebrated stochastic average gradient (SAGA) method, and its several existing and many new minibatch, reduced memory, and importance sampling variants. Our rate for SAGA with importance sampling is the current best-known rate for this method, resolving a conjecture by Schmidt et al (2015). The rates we obtain for minibatch SAGA are also superior to existing rates. Moreover, we obtain the first minibatch SAGA method with importance sampling.

This is joint work with Robert Mansel Gower (Telecom ParisTech) and Francis Bach (INRIA and Ecole Normale Superieure).

Frankl and Füredi conjectured (1989) that any r-uniform hypergraph, whose edges form an initial segment of length m in the colex ordering, maximises the Lagrangian among all r-uniform hypergraphs with m edges, for all r and m. We prove this conjecture for r=3 (and all sufficiently large m), thus improving results of Talbot (2002), Tang et al. (2016) and Tyomkyn (2017). For larger r, we show that the conjecture holds whenever $\left(\genfrac{}{}{0ex}{}{\mathrm{t-1}}{r}\right)$ ≤ m ≤ $\left(\genfrac{}{}{0ex}{}{\mathrm{t-1}}{r}\right)$ + $\left(\genfrac{}{}{0ex}{}{\mathrm{t-2}}{\mathrm{r-1}}\right)$ for some integer t (and m is large enough), thus improving a result of Tyomkyn. However, the conjecture is in fact false for general r>3 and m.

I will present an algorithmic question called the stochastic path problem, which is a multi-objective optimisation problem. My motivation for studying this problem is a connection with probabilistic automata of bounded ambiguity. There are more (open) questions than answers, and as customary nowadays I will construct a quasipolynomial time algorithm.

Based on a joint work with Cristian Riveros and James Worrell published in CONCUR'17.

As usual, P_n (n≥1) denotes the path on n vertices, and C_n (n≥3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P₇,C₄,C₅)-free graphs; in fact, we give a complete structural characterization of (P₇,C₄,C₅)-free graphs that do not admit a clique-cutset. We use this decomposition theorem to show that the class of (P₇,C₄,C₅)-free graphs is χ-bounded by a linear function (more precisely, every (P₇,C₄,C₅)-free graph G satisfies χ(G)≤3ω(G)/2, and to to construct polynomial-time algorithms that solve the optimal coloring, maximum weight clique, and maximum weight stable set problems for this class.

The talk is based on joint work with Kathie Cameron, Shenwei Huang and Vaidy Sivaraman.

A (proper) colouring of a graph is a vertex colouring where no two neighbouring vertices are coloured the same, and the chromatic number is the least number of colours where this is possible. Determining the chromatic number of G(n,p) is one of the classic challenges in random graph theory. For the case where p is constant, we will establish upper and lower bounds which are the first to match each other up to a term of size o(1) in the denominator. In particular, these bounds determine the average colour class size in an optimal colouring almost completely, answering a question by Kang and McDiarmid. We also consider a closely related graph parameter - the equitable chromatic number of the dense random graph G(n,m) - which can be determined exactly on a subsequence of the integers.

We develop a new technique for proving lower bounds in the setting of assymetric communication, a model that was introduced in the famous works of Miltersen (STOC '94) and Miltersen, Nisan, Safra and Wigderson (STOC '95). At the core of our technique is the first simulation theorem in the assymetric setting, where Alice gets a p \times n matrix x over F_2 and Bob gets an n-bit vector y. Alice and Bob need to evaluate f(x . y) for a boolean function f : {0,1}^p --> {0,1}; where x . y is the matrix-vector product. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C . n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost \Theta(C) for evaluating it.

As applications of this technique, we obtain the following results: (a) The first strong lower bounds against randomized data structure schemes for the one-bit output problem of Vector Matrix-Vector product over F_2. Moreover, our method yields strong lower bounds even when the data structure scheme has tiny advantage over random guessing. (b) The first lower bounds against randomized data structure schemes for two natural Boolean variants of Orthogonal Vector Counting. (c) We construct an assymetric communication problem and obtain a deterministic lower bound for it which is provably better than any lower-bound which might be obtained by the classical Richness method of Miltersen et al. (STOC '95). This seems to be the first known limitation of the Richness method in the context of proving deterministic lower bounds.

(This is joint work with Michal Koucky, Bruno Loff and Sagnik Mukhopadhyay.)

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and Jakub Tarnawski.

Economists have studied the theory and practice of auctions for decades. How can computer science contribute? Using the recent U.S. FCC double-auction for wireless spectrum as a case study, I'll illustrate the many answers: novel auction formats, algorithms for NP-hard problems, approximation guarantees for simple auctions, and communication complexity-based impossibility results.

The Graham-Pollak theorem states that to decompose the complete graph Kn into complete bipartite subgraphs we need at least n−1 of them. What happens for hypergraphs? In other words, suppose that we wish to decompose the complete r-graph on n vertices into complete r-partite r-graphs; how many do we need?

In this talk we will report on recent progress on this problem. This is joint work with Luka Milicevic and Ta Sheng Tan.

Labeling schemes seek to assign a label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. The goal is to minimize the maximum length of a label and (as a secondary goal) the time to evaluate the function. As a prime example, we might want to compute the distance between two nodes of a network using only their labels. We consider this question for two natural classes of networks: trees and planar graphs. For trees on n nodes, we design labels consisting of 1/4log^2(n) bits (up to lower order terms), thus matching a recent lower bound of Alstrup et al. [ICALP 2016]. One of the components used in our solution (and many others) is a labeling scheme for finding the nearest common ancestor of two nodes in a rooted tree. We present a novel interpretation of this question using the notion of minor-universal trees, which allows us to improve the 2.772log(n) upper bound of Alstrup et al. [SODA 2014] to 2.318log(n), and highlights a natural limitation of all known schemes.

For planar graphs, the situation of distance labeling is more complex. A major open problem is to close the gap between an upper bound of O(n^{1/2}log(n))-bits and a lower bound of O(n^{1/3})-bits for unweighted planar graphs. We show that, for undirected unweighted planar graphs, there is no hope to achieve a higher lower bound using the known techniques. This is done by designing a centralized structure of size ~O(min(k^2,(kn)^{1/2})) that can calculate the distance between any pair of designated k terminal nodes. We show that this size it tight, up to polylogarithmic terms, for such centralized structures. This is complemented by an improved upper bound of O(n^{1/2}) for labeling nodes of an undirected unweighted planar graph for calculating the distances.

Joint work with Ofer Freedman, Fabian Kuhn, Jakub Lopuszanski, Pat Nicholson, Konstantinos Panagiotou, Pascal Su, Przemyslaw Uznanski, Oren Weimann.

Two-player zero-sum games of infinite duration are used in verification to model the interaction between a controller (Eve) and its environment (Adam). The question usually addressed is that of the existence of a strategy for Eve that can maximize her payoff against any strategy of Adam. I will summarize recent work on an alternative solution concept: finding regret-minimal strategies of Eve, i.e. strategies that minimize the difference between her actual payoff and the payoff she could have achieved if she had known the strategy of Adam in advance. We give algorithms to compute the strategies of Eve that ensure minimal regret against an adversary whose choice of strategy is (i) unrestricted, (ii) limited to positional strategies, or (iii) limited to word strategies.

Understanding the distribution of subgraph counts has long been a central question in the study of random graphs. In this talk, we consider the distribution of the number of K_4 subgraphs, denoted by S_n in the Erdős Rényi random graph G(n,p). When the edge probability is a fixed constant in (0,1), a classical central limit theorem for S_n states that (S_n-mu_n)/\sigma_n$ converges in distribution to the standard Gaussian distribution. This convergence can however be shown to hold locally as well and we present a proof of the local convergence of S_n, which is joint work with O. Riordan.

How many induced cycles can a graph on n vertices contain? For sufficiently large n, we determine the maximum number of induced cycles and the maximum number of even or odd induced cycles. We also characterize the graphs achieving this bound in each case. This answers a question of Tuza, and a conjecture of Chvátal and Tuza from 1988. Joint work with Alex Scott.

Given an integer-valued matrix A of dimension l x k and an integer-valued vector b of dimension l, the Maker-Breaker (A,b)-game on a set of integers X is the game where Maker and Breaker take turns claiming previously unclaimed integers from X, and Maker's aim is to obtain a solution to the system Ax=b, whereas Breaker's aim is to prevent this.

When X is a random subset of {1,...,n} where each number is included with probability p independently of all others, we determine the threshold probability p_0 for when the game is Maker or Breaker's win, for a large class of matrices and vectors. This class includes but is not limited to all pairs (A,b) for which Ax=b corresponds to a single linear equation. The Maker's win statement also extends to a much wider class of matrices which include those which satisfy Rado's partition theorem.

Symbolic executions (and their recent variants called dynamic symbolic executions) are an important technique in automated testing. Instead of analysing only concrete executions of a program, one could treat such executions symbolically (i.e. with some variables that are not bound to concrete values) and use constraint solvers to determine this (symbolic) path feasibility so as to guide the path explorations of the system under test, which in combination with dynamic analysis gives the best possible path coverage. For string-manipulating programs, solvers need to be able to handle constraints over the string domain. This gives rise to the following natural question: what is an ideal decidable logic over strings for reasoning about path feasibility in a program with strings? This is a question that is connected to a number of difficult results in theoretical computer science (decidability of the theory of strings with concatenations, a.k.a., word equations) and long-standing open problems (e.g. decidability of word equations with length constraints). Worse yet, recent examples from cross-site scripting vulnerabilities suggest that more powerful string operations (e.g. finite-state transducers) might be required as first class citizens in string constraints. Even though putting all these string operations in a string logic leads to undecidability, recent results show that there might be a way to recover decidability while retaining expressivity for applications in symbolic execution. In this talk, I will present one such result from my POPL'16 paper (with P. Barcelo). The string logic admits concatenations, regular constraints, finite-state transductions, letter-counting and length constraints (which can consequently express charAt operator, and string disequality). I will provide a number of examples from the cross-site scripting literature that shows how a string logic can, for the first time, be used to discover a bug in or prove correctness of the programs. I will conclude by commenting on a new decision procedure for the logic that leads to an efficient implementation (POPL'18 with L. Holik, P. Janku, P. Ruemmer, and T. Vojnar) and a recent attempt to incorporate the fully-fledged replace-all operator into a string logic (POPL'18 with T. Chen, Y. Chen, M. Hague, and Z. Wu).

Automata are one of the simplest computational model, computing the well-known class of regular languages and enjoying a lot of nice properties. However, an automaton has only a "qualitative" behaviour: either it accepts a given input or rejects it. Weighted automata are a quantitative extension of automata, introduced in the 60's, which allow to compute values such as probabilities, costs, gains... In this talk, I will introduce this model, and describe the main (closed and open) problems in this field. I might also explain the link with the study of sets of matrices.

Evolutionary algorithms are popular general-purpose algorithms for optimisation and design that use search operators like mutation, crossover and selection to "evolve" a population of good solutions. In the past decades there has been a long and controversial debate about when and why the crossover operator is useful. The building-block hypothesis assumes that crossover is particularly helpful if it can recombine good "building blocks", i. e. short parts of the genome that lead to high fitness. However, all attempts at proving this rigorously have been inconclusive. As of today, there is no rigorous and intuitive explanation for the usefulness of crossover. In this talk we provide such an explanation. For functions where "building blocks" need to be assembled, we prove rigorously that many evolutionary algorithms with crossover are twice as fast as the fastest evolutionary algorithm using only mutation. The reason is that crossover effectively turns fitness-neutral mutations into improvements by combining the right building blocks at a later stage. This also leads to surprising conclusions about the optimal mutation rate.

Correspondence coloring, introduced by Dvorak and I in 2015, is a generalization of list coloring wherein vertices are given lists of colors and each edge is given a matching between the lists of its endpoints. So unlike in list or even ordinary coloring where adjacent vertices are not allowed to be colored the same, here we require that the colors of adjacent vertices are not matched along the edge. In this manner, correspondence coloring is list coloring where the 'meaning' of color is a local rather than global notion. Although results for correspondence coloring are interesting in their own right, in this talk we will focus on applying correspondence coloring to difficult problems from coloring and list-coloring to obtain new results; for example, for 3-list-coloring planar graphs without 4 to 8 cycles (joint work with Dvorak), on Reed's conjecture (joint work with Bonamy and Perrett) and on the list coloring version of Reed's conjecture (joint work with Delcourt).

How large can a set of integers be, if the equation a₁a₂...a_h=b₁b₂...b_h has no solution consisting of distinct elements of this set? How large can a set of integers be, if none of them divides the product of h others? How small can a multiplicative basis for {1, 2, ..., n} be? The first question is about a generalization of the multiplicative Sidon-sets, the second one is of the primitive sets, while the third one is the multiplicative version of the well-studied analogue problem for additive bases.

Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). In this talk I will show that the usual reductions preserving the complexity of the constraint satisfaction problem preserve also its proof complexity. As an application, I will present two gap theorems, which say that CSPs that admit small size refutations in some classical proof systems are exactly the constraint satisfaction problems which can be solved by Datalog.

This is joint work with Albert Atserias.

Reed conjectured in 1998 that the chromatic number of a graph should be at most the average of the clique number (a trivial lower bound) and maximum degree plus one (a trivial upper bound); in support of this conjecture, Reed proved that the chromatic number is at most some nontrivial convex combination of these two quantities. King and Reed later showed that a fraction of roughly 1/130000 away from the upper bound holds. Motivated by a paper by Bruhn and Joos, last year Bonamy, Perrett, and Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds, a signficant step towards the conjectured value of 1/2. Using new techniques, we show that the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. This result implies that 1/13 suffices for ordinary chromatic number as well. This is joint work with Luke Postle.

Planarity, bipartiteness, and acyclicity are basic graph properties with classic linear time recognition algorithms and the problems of testing whether a given graph has k vertices whose deletion makes it planar, bipartite, or acyclic, are fundamental NP-complete problems when k is part of the input.

However, it is known that for any fixed k, there is a linear time algorithm to test whether a graph is k vertices away from being planar or bipartite. On the other hand, it has remained open whether there is a similar linear time recognition algorithm for digraphs which are just 2 vertices away from being a DAG.

The subject of this talk is a new algorithm that, for every fixed k, runs in linear time and recognizes digraphs which are k vertices away from being acyclic, thus mirroring the case for planarity and bipartiteness. This algorithm is designed via a new methodology that can be used in combination with the technique of iterative compression from the area of Fixed-Parameter Tractability and applies to several ``cut problems’’ on digraphs. This is joint work with Daniel Lokshtanov (University of Bergen, Norway) and Saket Saurabh (The Institute of Mathematical Sciences, India).

Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. This is joint work with Gerco van Heerdt and Matteo Sammartino.

Hedetniemi's conjecture (1966) states that χ(G×H) = min(χ(G),χ(H)), for all graphs G,H (× being the tensor/direct/categorical product). The best we know is that the conjecture is true when χ(G×H) ≤ 3 (El-Zahar and Sauer 1985). The talk will focus on how this result is essentially just a proof of an analogous statement in topology, with one combinatorial step added. I will then survey some more connections with topology, questions about how deep they go, and some recent, more combinatorial approaches. No prior knowledge of topology is assumed.

In the Convex Body Chasing problem, we are given an initial point v₀ in R^d and an online sequence of n convex bodies F₁, … , F_n. When we receive F_i, we are required to move inside F_i. Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an Ω(√d) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open.

We consider the setting in which the convex bodies are nested: F₁ ⊃ … ⊃ F_n. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial’s conjecture. In this work, we give the first f(d)-competitive algorithm for chasing nested convex bodies in R^d.

This is joint work with Nikhil Bansal, Martin Bohm, Marek Elias and Grigorios Koumoutsos.

Let K be the field of real or p-adic numbers, and F(x) = (f_1(x), . . ., f_m(x)) be such that 1, f_1 , . . . , f_m are linearly independent polynomials with coefficients in K. In the present talk, we will prove that for the field K, the Borel chromatic number of of the Cayley graph of K^m with respect to these polynomials is infinite. The proof employs a recent spectral bound for the Borel chromatic number of Cayley graphs, combined with an analysis of certain oscillatory integrals over local fields. The talk should be accessible to non-experts.

In a recent breakthrough, Peter Keevash proved the Existence conjecture for combinatorial designs, which has its roots in the 19th century. In joint work with Daniela Kühn, Allan Lo and Deryk Osthus, we gave a new proof of this result, based on the method of iterative absorption. In fact, `regularity boosting’ allows us to extend our main decomposition result beyond the quasirandom setting and thus to generalise the results of Keevash. In particular, we obtain a resilience version and a minimum degree version. In this talk, we will present our new results within a brief outline of the history of the Existence conjecture and provide an overview of the proof.

A universal word for a finite alphabet A and some positive integer n is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well known and is easy to prove that universal words exist for any A and n. The notion of universal words was extended to other combinatorial structures (admitting encoding by words). Universal partial words are words that in addition to the letters from A may contain an arbitrary number of a special "joker" symbol, which can be substituted by any letter from A. The study of universal partial words was initiated recently. Such words allow shortening universal words. In my talk, I will discuss a number of existence and non-existence results related to universal partial words.

This is joint work with Herman Chen, Torsten Mutze and Brian Sun.

This talk focuses on the current challenges in computing distances and shortest paths on distributed networks (the CONGEST model), in particular exact algorithms and the directed case. I will survey previous results and techniques, and try to point out where the previous techniques fail, and where major new ideas are needed.

This talk will touch results I (co)-authored in STOC 2014 and STOC 2016, among others.

The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. I discuss sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs, and consider various applications of these lemmas.

Joint work with Peter Allen, Julia Böttcher, Hiep Hàn and Yoshiharu Kohayakawa.

Boolean valued constraint satisfaction problems (VCSPs) are discrete optimization problems with the goal to find an assignment of labels {0, 1} to variables that minimizes the objective function given as a sum of constant-arity constraints. In the surjective setting, an assignment is in addition required to use each label at least once. For example, the minimum cut problem falls within this framework. We give a complexity classification of Boolean surjective VCSPs parameterized by the set of available constraints.

The talk will be about two-player, zero-sum, concurrent, mean-payoff games played on graphs, classically called stochastic games. A stochastic game consists of a set of matrix games (that is games like rock-paper-scissors, where players act simultaneously). The game is over an infinite sequence of rounds and in each round one of the matrix games is played, and depending on the players joint choice and the matrix game, some reward is given and some matrix game is selected for the next round. The outcome of the game is given as the average of the rewards. Stochastic games has the annoying property that they are hard to play even near-optimally in the sense that the memory usage of even epsilon-optimal strategies (and optimal strategies need not even exist) grows unbounded as a function of the round number. The talk will focus on two questions related to stochastic games:

(1) Assume without loss of generality that all rewards are in [0,1], can we find the sub-set of matrix games, such that for each of those matrix games, there is an epsilon-optimal, finite-memory strategy that ensures value 1-epsilon for all epsilon>0? This problem is sometimes called the (finite-memory) value 1 problem (or limit-sure). I present an algorithm for that problem with polynomial running time. While the problem has not been considered for general stochastic games before, it has been considered for many special cases thereof (in each special case considered, if any strategy ensured value 1-epsilon, then a strategy without memory did as well). The algorithm also shows that if there exist a finite-memory strategy ensuring value 1-epilson, then there exist one ensuring 1-epsilon that did not use memory at all and the algorithm also finds such a strategy.

(2) Next, if we are not so lucky that the right start matrix game has a epsilon-optimal, finite-memory strategy, it would at least be nice to use as little memory as possible (as a function of time). That way, if we are forced to follow such a strategy we can at least add space for the strategy slowly. I present a new family of strategies for stochastic games that ensures that the strategy only needs O(log log T) bits of memory in round T (previous known strategies used O(log T) bits of memory in round T).

The talk will not assume prior knowledge about stochastic games, and is based on my paper from SODA 2015 and my paper from SAGT 2016. Both papers can be found on my homepage at http://Rasmus.Ibsen-Jensen.com

A central theorem in combinatorics is Sperner’s Theorem, which determines the maximum size of a family in the Boolean lattice that does not contain a 2-chain. Erdős later extended this result and determined the largest family not containing a k-chain. Erdős and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result.

This question was resolved for 2-chains by Kleitman in 1966, who showed that amongst families of size M in the Boolean lattice, the number of 2-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all k, not just 2. The best result on this question is due to Das, Gan and Sudakov who showed roughly that Kleitman’s conjecture holds for families whose size is at most the size of the k+1 middle layers of the Boolean lattice. Our main result is that for every fixed k and epsilon, if n is sufficiently large then Kleitman’s conjecture holds for families of size at most (1-epsilon)2^n, thereby establishing Kleitman’s conjecture asymptotically. Our proof is based on ideas of Kleitman and Das, Gan and Sudakov.

In the presentation, we consider extensions of dynamic programming approach to the investigation of decision trees as algorithms for problem solving, as a way for knowledge extraction and representation, and as classifiers which, for a new object given by values of conditional attributes, define a value of the decision attribute. These extensions allow us (i) to describe the set of optimal decision trees, (ii) to count the number of these trees, (iii) to make sequential optimization of decision trees relative to different criteria, (iv) to find the set of Pareto optimal points for two criteria, and (v) to describe relationships between two criteria. The applications include the minimization of average depth for decision trees sorting eight elements (this question was open since 1968), improvement of upper bounds on the depth of decision trees for diagnosis of 0-1-faults in read-once combinatorial circuits over monotone basis, existence of totally optimal (with minimum depth and minimum number of nodes) decision trees for Boolean functions, study of time-memory tradeoff for decision trees for corner point detection, study of relationships between number and maximum length of decision rules derived from decision trees, study of accuracy-size tradeoff for decision trees which allows us to construct enough small and accurate decision trees for knowledge representation, and decision trees that, as classifiers, outperform often decision trees constructed by CART. The end of the presentation is devoted to the introduction to KAUST.

An arena is a finite directed graph whose vertices are divided into two classes, i.e. squares and circles; this forms the basic playground for many infinite 2-player pebble games. In Update Games the square player aims at moving the pebble so to visit all vertices of the arena infinitely often, while player circle works against. It is known that deciding who’s the winner in a given Update Game costs O(mn) time, where n is the number of vertices and m is that of arcs. We present an algorithm for solving that problem in O(m+n) linear time. The algorithm builds on a generalization, from directed graphs to arenas, of the depth-first search (DFS) and the strongly-connected components (SCCs) decomposition, taking inspiration from Tarjan’s SCCs classical algorithm.

Property testing (for a property P) asks for a given input, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of big data.

We extend the bounded degree model of property testing from graphs to relational structures, and we show that every property definable in first-order logic is testable with a constant number of queries in polylogarithmic time. On structures of bounded tree-width, a similar statement holds for monadic second-order logic.

This is joint work with Frederik Harwath.

The primal-dual method is a general technique that is widely used to design efficient (static) algorithms for optimization problems. We present the first application of this technique in a dynamic setting.

We consider the problem of maintaining an approximately maximum matching in a dynamic graph. Specifically, we have an input graph G = (V, E) with n nodes. The node-set of the graph remains unchanged over time, but the edge-set is dynamic. At each time-step an adversary either inserts an edge into the graph, or deletes an already existing edge from the graph. The goal is to maintain a matching of approximately maximum size in G with small update time.

We present a clean primal-dual algorithm for this problem that maintains a (2+epsilon)-approximate maximum fractional matching in O(log n) amortized update time. We also describe several extensions to this basic framework, which allow us to obtain new efficient dynamic algorithms for maintaining a (2+\epsilon)-approximate maximum integral matching in O(poly log n) amortized update time, and a (2+epsilon)-approximate maximum fractional matching in O(log^3 n) worst case update time.

Joint work with Monika Henzinger, Giuseppe Italiano and Danupon Nanongkai.

In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained.

In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents’ current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents' bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once.

In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a 1/3 approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an Ω(1/ log m) approximation in case of m items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than an o(log log m/ log m) fraction of the optimal social welfare.

Joint work with Thomas Kesselheim

The paper is available from: http://paulduetting.com/pubs/SODA17.pdf

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

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

For k∈ N, k-coloring of a graph G is a partition V₁, ..., V_k of its vertex set into k independent sets (i.e., sets with no edges between their elements). Given a graph G, we might want to know if it admits a k-coloring - and this question leads to a great body of work in graph theory. To complicate the matters further, we can require the sets V₁, ..., V_k to have some additional "nice" properties. For instance, if the vertex set of G is the unit interval [0,1], can the sets V₁, ..., V_k be Lebesgue-measurable (or, even better, Borel)? The short answer is, not always, and understanding the extent to which classical combinatorial results can be adapted for the Borel and measurable settings is the premise of the recently emerged field of Borel combinatorics, which has already found many applications in descriptive set theory, ergodic theory, probability theory, and the study of graph limits, to name a few. In this talk I will try to give a brief introduction to this fascinating area and to explain how the Lovász Local Lemma, a classical tool in probabilistic combinatorics, can be used to obtain results in the measurable framework.

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for (diamond,P₁+2P₂)-free graphs. Our technique for handling this case is to reduce the graph under consideration to a k-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of (H₁,H₂)-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of (H₁,H₂)-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.

Joint work with François Dross and Daniël Paulusma.

Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by [n]={1,2,...,n}, with edges directed towards the root. Each node of the tree has space for a single particle (we think of them as cars). A number m<=n of cars arrives one by one, and car i wishes to park at node S_i, 1<=i<=m, where S₁, S₂, ..., S_m are i.i.d. uniform random variables on [n]. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until the first time it encounters an empty space, in which case it parks there; otherwise, it leaves the tree. Let A_n,m denote the event that all m cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Set m = [an]. Then if a<=1/2, P(A_n,[an]) tends to (1-2a)^1/2/(1-a), whereas if a>1/2 we have P(A_n,[an]) tending to 0. (In fact, they proved more precise asymptotics in n for a>1/2.) In this talk, I will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Time permitting, I will also discuss some generalisations.

Joint work with Michał Przykucki (Oxford).

Shared vehicle systems, such as those for bike-sharing (e.g., Citi Bike in NYC, Velib in Paris), car-sharing (e.g., car2go, Zipcar) and ride-sharing (Uber, Lyft, etc.) are fast becoming essential components of the urban transit infrastructure. The technology behind these platforms enable fine-grained monitoring and control tools, including good demand forecasts, accurate vehicle-availability information, and the ability to do dynamic pricing and vehicle repositioning. However, owing to their on-demand nature and the presence of network externalities (wherein setting prices at one place affects the supply at all other locations), optimizing the operations of such systems is challenging.

In this work, we describe how such systems can be modeled using queueing-network models and present a unifying framework for data-driven pricing and optimization. Our approach provides efficient algorithms with rigorous approximation guarantees under a variety of controls (pricing, empty-vehicle repositioning, demand redirection) and for a wide class of objective functions (including welfare and revenue, and also multi-objective problems such as Ramsey pricing).

Based on joint work with Sid Banerjee and Thodoris Lykouris at Cornell

Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d₀,d₁,d₂,d₃) that are arbitrary close to 3-vertex graph densities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d₀,d₃) plane. We determine the projections of the set S to all the remaining planes.

This is joint work with Roman Glebov, Ping Hu, Tamás Hubai, Daniel Král' and Jan Volec.

A graph in a certain class is said to be universal if all elements of the class embed to it according to a specified notion of embedding, may it be strong, weak or homomorphic embeddings. For example, any class of graphs that contains a clique of the size equal to the largest size of an element of the class, if such a largest size exists, is universal for that class under weak embeddings. The question becomes more complicated when one discusses classes of graphs that omit cliques, or if one changes the notion of embedding. For example, there is no universal graph for all countable graphs that omit an infinite clique, yet there is a strongly universal countable graph in the class of all countable graphs (the random graph). We shall discuss what happens at uncountable infinite cardinals, where we get independence results, open questions and, this is what was surprising to us, at certain of them just straight negative answers without any additional axioms of set theory used. The proof is simple and we shall show it during the talk.

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

This is joint work with Alina Ene, Huy L. Nguyen and Justin Ward.

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.

Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

Joint work with Martin Böhm, Jarosław Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang and Pavel Veselý, appeared at ESA 2016.

Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. There are other problems, however, which can be more naturally phrased in terms of disjoint independent sets in hypergraphs. We develop an analogue of the container theorem of Balogh, Morris and Samotij for tuples of disjoint independent sets in hypergraphs. We also give several applications of this theorem to Ramsey-type problems. For example, we generalise the random Ramsey theorem of Rödl and Ruciński by providing a resilience analogue. This result also implies the random version of Turán's theorem due to Conlon and Gowers, and Schacht.

This is joint work with Robert Hancock and Katherine Staden.

We consider the class of graphs that does not contain as induced subgraphs chordless cycles of odd length greater than 3, their complements and chordless cycles of length 4 (square-free Berge graphs). We present a purely-graph theoretical algorithm that produces an optimal coloring for the graphs in this class. This is joint work with Chudnovsky, Lo, Maffray and Trotignon.

This is a subclass of perfect graphs, that have been extensively studied in the last 50 years. In 1981 Grötschel, Lovász and Schrijver showed that perfect graphs can be optimally colored in polynomial time. Their algorithm uses the ellipsoid method. The last big open problem in the area is to find a purely combinatorial polynomial time coloring algorithm for perfect graphs.

An online algorithm receives its input piece-by-piece in a serial fashion. Upon reception of a piece of the input, it has to irrevocably decide how to process this piece of data. Since the online algorithm can base its decisions only on what it has seen in the past, and, in particular, has no information about the future, it is often difficult or impossible to take good decisions. For many problems, access to randomness helps to avoid that the algorithm always takes the wrong decisions.

Suppose that we provide the online algorithm with additional knowledge about the future (= advice). Clearly, if enough information is given, we can obtain optimal solutions. However, does it help if we grant only very few advice bits to the algorithm? How much advice is needed to outperform any randomized online algorithm? In this work, we study these questions with regards to the maximum bipartite matching problem.

This is joint work with Christoph Dürr (Université Pierre et Marie Curie, Paris) and Marc Renault (Université Paris Diderot, Paris).

We will talk about recent work which shows that there are infinitely many primes with no 7 in their decimal expansion. (And similarly with 7 replaced by any other digit.) This shows the existence of primes in a thin set of numbers, which is typically very difficult. The proof relies on a fun mixture of number theory, discrete Fourier analysis and combinatorial geometry, amongst other things.

Hidden Markov Chains (HMCs) are commonly used mathematical models of probabilistic systems. They are employed in various fields such as speech recognition, signal processing, and biological sequence analysis. We consider the problem of distinguishing two given HMCs based on an observation sequence that one of the HMCs generates. More precisely, given two HMCs and an observation sequence, a distinguishing algorithm is expected to identify the HMC that generates the observation sequence. Two HMCs are called distinguishable if for every ε>0 there is a distinguishing algorithm whose error probability is less than ε. We show that one can decide in polynomial time whether two HMCs are distinguishable. Further, we present and analyze two distinguishing algorithms for distinguishable HMCs. The first algorithm makes a decision after processing a fixed number of observations, and it exhibits two-sided error. The second algorithm processes an unbounded number of observations, but the algorithm has only one-sided error. The error probability, for both algorithms, decays exponentially with the number of processed observations. We also provide an algorithm for distinguishing multiple HMCs. Finally, we discuss an application in stochastic runtime verification.

Joint work with A. Prasad Sistla.

Let X denote the number of k-term arithmetic progressions in a random subset of Z/NZ or {1,...,N}. We determine, in certain ranges of parameters, the probability that X exceeds its expectation by a constant factor. ⁡Recently, Chatterjee and Dembo reduced the problem, at least for k=3, to a natural variational problem. We solve this variational problem asymptotically, thereby obtaining the large deviation rate. More generally, for all k, using the inverse theorem for the Gowers norms, we determine the rate as long as p tends to 0 extremely slowly.

Joint work with Bhaswar B. Bhattacharya, Shirshendu Ganguly, and Xuancheng Shao.

One-counter automata (OCA) are finite-state automata with a counter that supports increments, decrements, and tests for zero. They correspond to an intermediate class between regular and context-free languages and are suitable for modeling ``counting'' phenomena. However, reasoning about OCA is often intractable: for example, language equivalence is undecidable for nondeterministic OCA, and for deterministic OCA it took 40 years to prove the existence of short distinguishing words. In this talk, I will give a review of reasoning tasks for OCA and discuss new tractability results:

1. shortest paths between configurations of OCA are of at most quadratic length;
2. the Parikh image and sub-/superword closures of the language are accepted by small nondeterministic finite automata.

The list chromatic number of a hypergraph is defined in the same way as for a graph: it is the smallest number k such that, if every vertex is given a list of k colours, then each vertex can choose a colour from its list so that no edge is monochromatic. One of the successes of the recently discovered "container method" was to show that the list colouring number of an r-uniform hypergraph is at least c_r log d, where d is the average degree. But is the container method giving the best answer here? We describe a colouring algorithm based on "preference orders" which correctly determines the list chromatic number of hypergraphs having a certain property. Hypergraphs with this property include those generated at random, which are expected to be worst-case examples for the general problem.

Joint work with Ares Meroueh.

A fundamental theorem of Wilson states that, for every graph F, the edge-set of every sufficiently large clique (satisfying a trivially necessary divisibility condition) has a decomposition into copies of F. One of the main open problems in this area is to determine the minimum degree threshold which guarantees an F-decomposition in an incomplete host graph. We solve this problem for the case when F is bipartite and make significant progress towards the general case.

This is joint work with Stefan Glock, Daniela Kühn, Richard Montgomery and Deryk Osthus.

Graph bootstrap percolation, known also as weak saturation, is a simple cellular automaton introduced by Bollobás in 1968. Given a graph H and a subset G of E(K_n) we initially infect all edges in G and then, in consecutive steps, we infect every edge e that completes a new infected copy of H in K_n. We say that G percolates if eventually every edge in K_n is infected.

In this talk, for H = K_r, we discuss the running time of the process until it percolates. Treating this as an extremal question, we obtain bounds on the maximum running time of the process when the initial graph G is chosen deterministically. For G = G_n,p, we give threshold densities p=p(n,r,t) such that G_n,p percolates in exactly t time steps of the K_r-bootstrap process with high probability.

Based on joint work with Béla Bollobás, Oliver Riordan, and Julian Sahasrabudhe, and with Karen Gunderson and Sebastian Koch.

A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore can be characterized in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit disk graphs very little is known about minimal forbidden induced subgraphs for this class. We found only finitely many minimal non unit disk graphs in the literature. In this paper we study in a systematic way forbidden induced subgraphs for the class of unit disk graphs. We develop several structural and geometrical tools, and use them to reveal infinitely many new minimal non unit disk graphs. Further we use these results to investigate structure of co-bipartite unit disk graphs. In particular, we give structural characterization of those co-bipartite unit disk graphs whose edges between parts form a C₄-free bipartite graph, and show that bipartite complements of these graphs are also unit disk graphs. Our results lead us to propose a conjecture that the class of co-bipartite unit disk graphs is closed under bipartite complementation.

Based on joint work with Aistis Atminas.

Many processes found in nature, for example dielectric breakdown cascades, Hele-shaw flow and electrodeposition, have fascinating similar behaviors such as the formation of fractal-like arms. We consider a classical random process of aggregation on Z^d, which belongs to a class of models introduced in the physics and chemistry literature to better understand how fractal structures arise in nature. At each vertex of Z^d, initially place one particle with probability mu, independently of other vertices. In addition, an aggregate will grow through Z^d. The aggregate initially consists only of the origin. Particles move as continuous time simple random walks obeying the exclusion rule (so that each vertex has no more than one particle at any time). The aggregate grows indefinitely by attaching particles to its surface whenever a particle attempts to jump onto it. Once a particle is attached to the aggregate, it becomes part of the aggregate and does not move anymore. The only rigorous results previously known about this process were restricted to 1 dimension. In this work we show that, for dimensions d>1, if the initial density of particles mu is large enough, then with positive probability the aggregate grows with positive speed, reaching out to distance of order t by time t.

This is a joint work with Vladas Sidoravicius.

Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over words. We study the expressiveness and closure properties of copyless CRA. In particular we compare this model with the well-know model of weighted automata. Weighted automata can be naturally characterized by a subfragment of weighted logic, a quantitative extension of MSO introduced by Droste and Gastin. Our results show that a similar characterization of copyless CRA seems to be unlikely. We introduce a new quantitative logic, which turns out to be equally expressive to a natural subclass of copyless CRA.

Based on joint work with Cristian Riveros.

Does a given regular language over an alphabet of integer vectors contain a word such that (1) the sum of every prefix is non-negative and (2) the sum of the whole word is 0 ?

This problem, known as the reachability problem for vector addition systems with states, has widespread applications in logic, formal languages, control theory, and the verification of concurrent processes. It was first shown to be decidable already in the early 80s, but its exact complexity remains elusive to date.

In this talk I will recall the status quo regarding the complexity of the reachability problem, mostly focussing on the subproblems for fixed and small dimensions.

I will present our recent result on the two-dimensional case that the length of shortest reachability certificates is polynomial in the largest integer and the size of the NFA defining the input language. This complements a result by Blondin et. al. (LICS'15) and shows that the 2-dim. reachability problem is PSPACE-complete when numbers are encoded in binary and NL-complete if the input is given in unary.

We consider the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph classes. If an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder.

We give a structural characterization of graph classes which are FO-interpretable in graph classes of bounded degree. This characterization allows us to efficiently compute such an interpretation for an input graph. As a consequence, we obtain an FPT algorithm for FO model checking of graph classes FO interpretable in graph classes of bounded degree. The approach we use to obtain these results may also be of independent interest.

Based on joint work with P. Hliněný, D. Lokshtanov, J. Obdržálek and M. S. Ramanujan.

We consider the problem of finding a Hamilton cycle in a uniform hypergraph of large minimum codegree. This is an area which has been widely studied over the years, with existing results including Dirac's classical theorem that any graph G on n>=3 vertices with minimum degree delta(G)>=n/2 admits a Hamilton cycle, and Röodl, Ruciński and Szemerédi's analogous theorem for k-uniform hypergraphs (k-graphs) H with minimum codegree delta(H)>=n/2+o(n).

Our attention is focussed on k-graphs with minimum codegree slightly below the aforementioned minimum codegree threshold. For tight cycles, we show that the determining the existence of a Hamilton cycle is NP-hard even in k-graphs H with minimum codegree delta(H)>=n/2-C , where C is a constant depending only on k. On the other hand, we demonstrate significantly different behavior for looser cycles. Indeed, we prove the existence of a constant eps such that we can find a Hamilton 2-cycle in polynomial time (or give a certificate that no such cycle exists) in a 4-graph H with delta(H)>=n/2-eps*n. This is achieved through a structural theorem which precisely characterises all 4-graphs H with delta(H)>=n/2-eps*n which do not contain a Hamilton 2-cycle.

This is joint work with Frederik Garbe (University of Birmingham).

Erdős, Faudree and Rousseau conjectured in 1992 that for every k>=2 every graph with n vertices and n²/4+1 edges contains at least 2n²/9 edges that occur in an odd cycle of length 2k+1. We disprove this conjecture for k=2 by showing a graph with (2+sqrt(2))n²/16 edges in pentagons. We prove that asymptotically this is the best possible constant in this case. For the remaining case k>=3, we prove that asymptotically the conjecture is true. The main tool used in the proofs is the flag algebra method applied in a specific two-colored setting.

Joint work with Andrzej Grzesik and Jan Volec.

In order to define a class of graphs, we often say that the class consists of exactly those graphs which admit a specific (e.g. geometric) representation. For instance, interval graphs are the graphs that can be represented by real intervals so that every vertex is assigned an interval and the edges are the pairs of intervals that intersect. The recognition problem for such a class of graphs asks whether a graph provided in the input belongs to the class. Most recognition algorithms also produce an appropriate representation for positive instances. The partial representation extension problem generalizes the recognition problem: given a graph G, a subset S of V(G), and a representation R of the induced subgraph G[S], it asks whether G admits a representation that extends R, that is, whose restriction to S is equal to R.

Partial representation extension problems have been introduced in 2011 by Klavík, Kratochvíl and Vyskočil, who provided a polynomial-time algorithm for extending partial representations of interval graphs. In general, recognition algorithms for classes which allow a compact structural description of all valid representations of a graph (such as the PQ-tree for interval graphs or the modular decomposition for permutation graphs) are usually easy to generalize to solve the partial representation extension problem as well. However, for many natural classes of graphs like circular-arc graphs or trapezoid graphs no such structural description is known. In a joint work with Tomasz Krawczyk, we propose a way of overcoming this difficulty; in particular, we provide a polynomial-time partial representation extension algorithm for the class of trapezoid graphs.

In this talk, I will briefly survey results on partial representation extension problems for various classes of graphs. Then, for some example classes, I will explain what the structural description of all valid representations looks like and how it is useful for extending partial representations. Finally, I will present some ideas behind the above-mentioned algorithm for trapezoid graphs.

Networks are ubiquitous in today’s world. Any time we make observations about people, places, or things and the interactions between them, we have a network. Yet a quantitative understanding of real-world networks is in its infancy, and must be based on strong theoretical and methodological foundations. The goal of this talk is to provide some insight into these foundations from the perspective of nonparametric techniques in relation to subgraph count statistics, in particular how tradeoffs between model complexity and parsimony can be balanced to yield practical algorithms with provable properties.

Programs with dynamic allocation are able to create and use an unbounded number of fresh resources, such as references, objects, files, etc. We propose History-Register Automata (HRA), a new automata-theoretic formalism for modelling such programs. HRAs extend the expressiveness of previous approaches and bring us to the limits of decidability for reachability checks. The distinctive feature of our machines is their use of unbounded memory sets (histories) where input symbols can be selectively stored and compared with symbols to follow. In addition, stored symbols can be consumed or deleted by reset. We show that the combination of consumption and reset capabilities renders the automata powerful enough to imitate counter machines, and yields closure under all regular operations apart from complementation. We moreover examine weaker notions of HRAs which strike different balances between expressiveness and effectiveness. This is joint work with Radu Grigore.

There have been many results recently on the probability of large deviations of subgraph counts in the Erdos-Renyi random graph G(n,p). In this talk we discuss smaller deviations in subgraph counts. And, as we shall see, the correct context for these results is G(n,m) rather than G(n,p).

Based on joint work with Christina Goldschmidt and Alex Scott.

We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m machines receives n data points from a d-dimensional Gaussian distribution with unknown mean θ which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean θ. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least Ω(min{n,d}m), where n is the number of observations that each machine receives and d is the ambient dimension. We also give the first optimal simultaneous protocol in the dense case for mean estimation.

As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

This is joint work with Mark Braverman, Ankit Garg, Tengyu Ma, and David P. Woodruff

A sequence of graphs is called locally convergent if their features observable by local sampling are getting indistinguishable in the limit. This concept is most useful for bounded degree graphs. We observe how graph polynomials like the chromatic or matching polynomial behave on such a sequence of graphs. Are they convergent in some regard? What would be a suitable notion of convergence?

(Joint work with different subsets of Miklós Abért and Péter Csikvári.)

A map is a cellular decomposition of a surface, or, equivalently, a 2-cell embedding of a graph on a surface. A map is regular if its automorphism group is transitive, and hence regular, on flags (vertex-edge-side triples of mutually incident elements). If the supporting surface of a map is orientable, the map is orientably regular if its group of all orientation-preserving automorphisms is transitive, and hence regular, on arcs (edges with a direction). Regular and orientably regular maps are a natural generalisation of Platonic solids to arbitrary surfaces.

At an algebraic level, regular and orientably regular maps can be identified with the corresponding automorphism groups, which turn out to be quotients of the well-known triangle groups. This gives rise to rich connections between the theory of regular maps and group theory, hyperbolic geometry, Riemann surfaces and Galois theory.

In the talk we will discuss the state-of-the-art of classification of regular and orientably regular maps with a given underlying graph, supporting surface, or automorphism group, and outline open problems in this area of research.

In this talk, I will discuss certain class of samplers for dynamic data that are known as L_p samplers. Formally, given a finite stream of updates (additions and subtraction) on the coordinates of an underlying vector x in R^n, an L_p sampler outputs a random coordinate where the probability of picking the i-th coordinate is |x_i|^p/||x||_p^p. In particular for p=1, each coordinate is sampled proportional to its weight |x_i|, while For p=0, the sampler simply outputs a random non-zero coordinate.

Relaxing the requirements and for p in [0,2), it has been shown there are approximate L_p samplers that output the i-th coordinate with probability O(|x_i|^p/||x||_p^p) using only O(log^2n) bits of space.

In this talk, I will discuss the general idea behind such samplers and present two applications in finding duplicates and dynamic graph problems. If time permits, I also show an Omega(log^2 n) lower bound for sampling from 0,+-1 vectors that proves the tightness of the upper bound in terms of dependence on n. In conclusion, I will mention some open questions and motivations for further work in this area.

The major part of this talk will be based on a joint work with Mert Saglam and Gabor Tardos published in PODS 2011.

A closed word, also referred to as a periodic-like word or complete first return, is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special. We show that a word of length n contains at least n+1 distinct closed factors. We also characterise words containing exactly n+1 closed factors. Furthermore, we show that a word of length n can contain Θ(n²) many distinct closed factors.

On the algorithmic side, we consider factorising a word into its longest closed factors and present a linear time algorithm for this problem. In addition, we construct a closed factor array, which holds for every position in the word, the longest closed factor starting at that position. We describe our technique that runs in O(n log n/ log log n) time.

Heat kernels are one of the most fundamental concepts in physics and mathematics. In physics, the heat kernel is a fundamental solution of the heat equation and connects the Laplacian operator to the rate of heat dissipation. In spectral geometry, many fundamental techniques are based on heat kernels. In finite Markov chain theory, heat kernels correspond to continuous-time random walks and constitute one of the most powerful techniques in estimating the mixing time.

In this talk, we will briefly discuss this line of research and its relation to heat kernels in graphs. In particular, we will see how heat kernels are used to design the first nearly-linear time algorithm for finding clusters in real-world graphs. Some interesting open questions will be addressed as well.

This is based on the joint work with Richard Peng (MIT), and Luca Zanetti (University of Bristol). Parts of the results of this talk appeared in COLT 2015.

The growth rate function for a minor-closed class of matroids is the function h(n) whose value at an integer n is the maximum number of elements in a simple matroid in the class of rank at most n; this can be seen as a measure of the density of thematroids in the class. A theorem of Geelen, Kabell, Kung and Whittle implies that h(n), where finite, grows either linearly, quadratically, or exponentially with base equal to some prime power q, in n. I will discuss growth rate functions for classes of theexponential sort, determining the growth rate function almost exactly for various interesting classes and giving a theorem that essentially characterises all such functions. No knowledge of matroid theory will be assumed.

In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the `percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.

In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges. Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph.

We shall prove that, for a large class of widely studied rules (so-called bounded-size rules), the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process. For example, assuming ε³n→∞ and ε→0 as n→∞, the size of the largest component after step t_cn±εn whp satisfies L₁(t_cn-εn)∼Dε^-2log(ε³n) and L₁(t_c n+εn)∼dεn, where t_c,D,d>0 are rule-dependent constants (in the Erdös-Rényi process we have t_c=D=1/2 and d=4).

Based on joint work with Oliver Riordan.

A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a "local double counting" strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem. In our case, the optimization problem deals with partition functions of trees weighted by a supermultiplicative functional.

This is joint work with Guillaume Chapuy.

Over the past decade a number of parallel systems such as MapReduce, Hadoop, and Dryad have become widely successful in practice. In this talk, I will present a new algorithmic framework for geometric graph problems for these kinds of systems. Our algorithms produce approximate solutions for problems such as Minimum Spanning Tree (MST) and Earth-Mover Distance (EMD). Provided the underlying set of points lies in a space of constant dimension, only a constant number of rounds is necessary, while the total amount of space and communication remains linear in the size of the data. In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem, despite drawing significant attention in recent years.

Our algorithmic framework has implications beyond modern parallel systems. For example, it yields a new algorithm for approximating EMD in the plane in near-linear time. We note that while recently Sharathkumar and Agarwal (STOC 2012) have developed a near-linear time algorithm for (1+epsilon)-approximating EMD, our approach is fundamentally different and also solves the transportation cost problem, which was raised as an open question in their work.

Joint work with Alexandr Andoni, Aleksandar Nikolov, and Grigory Yaroslavtsev.

The sphere packing problem asks how large a fraction of R^n can be covered with congruent balls if they are not allowed to overlap (except tangentially). In this talk, I’ll survey what’s known in high dimensions, with particular attention to the role of symmetry, and I’ll highlight some open problems on which progress should be possible.

There are several notions of convergence for sequences of bounded degree graphs. One such notion is left convergence (also known as local or Benjamini-Schramm convergence), which is based on counting neighborhood distributions. Another notion is right convergence, based on counting homomorphisms to a target (weighted) graph. We introduce some of these notions. Borgs, Chayes, Kahn and Lovász showed that a sequence of bounded degree graphs is left convergent if and only if it is right convergent for certain target graphs H with all weights (including loops) close to 1. We will give a short alternative proof of this statement.

We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.

Mantel’s theorem tells us precisely how many edges a triangle-free graph may contain. We will consider some of the many analogues and extensions of this result, old, new and conjectured. New results are joint work with Rahil Baber and Adam Sanitt.

We study the problem of allocating a set of indivisible items among agents with additive valuations with the goal of maximizing the Nash social welfare objective, i.e., the product of the agents' valuations, a problem which is known to be NP-hard. Our main result is the first algorithm that guarantees a constant factor approximation for the average Nash social welfare. We first observe that the integrality gap of the convex program relaxation can be arbitrarily high so we propose a different fractional solution which we use as a guide to define an appropriate rounding which then leads to the constant factor approximation algorithm.

An interesting contribution of our analysis is the fractional solution that we use. The dual variables of the convex program that computes the Nash social welfare-maximizing fractional allocation can be interpreted as prices, and the fraction of the item allocated to each agent corresponds to how much the agent is spending on that item. Using this interpretation, we define a fractional solution that restricts the amount of spending that can go into any given item, thus keeping the highly demanded items under-allocated, and forcing the agents to spend on less desired items. As a result, the induced prices of this novel allocation reveal more information regarding how the less desired items should be allocated.

This is joint work with Vasilis Gkatzelis.

Decision problems with a non-elementary complexity occur naturally in logic, combinatorics, formal language, verification, etc., with complexities ranging from simple towers of exponentials to Ackermannian and beyond. Somewhat surprisingly, we lack the definitions of classes and reductions that would allow to state completeness results at such high complexities. We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many non-elementary problems.

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the optimal decomposition results for dense random graphs into (i) cycles and edges, (ii) paths and (iii) linear forests. There is also an interesting connection to the overfull subgraph conjecture on edge-colourings of graphs. We actually derive (i)-(iii) from quasirandom versions of our results.

The results are joint work with Stefan Glock and Deryk Osthus.

For a handful of problems (including some of the "flagship problems" of parameterized complexity), very efficient FPT algorithms can be constructed using using the LP-relaxation of the problem. However, this approach requires the LP to have some very restrictive properties that only a few LP-relaxations have, namely half-integrality and a technical condition known as persistence. (Prior to the work presented here, we knew of essentially two problems with such LP-relaxations, namely Vertex Cover and Node Multiway Cut). It was also not clear how to look for more compatible polytopes.

We circumvented this problem by observing that a half-integral LP relaxation corresponds to a polynomial-time solvable discrete problem relaxation to a larger domain, e.g., Vertex Cover can be efficiently minimised over the solution space {0, 1/2, 1}^n, which corresponds to optimisation over a domain of size 3. This lets us rephrase the existence of "useful relaxations" in the language of so-called Valued CSP problems.

In particular, we show that the LP-relaxations for Vertex Cover and Node Multiway Cut are special cases of a class of relaxations known as k-submodular functions, and use this class to give improved FPT algorithms for several other problems, including the first 2^O(k)-time algorithm for the problems Group Feedback Vertex Set and Subset Feedback Vertex. This is based on work from SODA 2014.

If time allows, I will also give a quick look at a direct combinatorial condition that provides an extension of this work.

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relationalstructures - culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [LICS'14] initiated the study of the complexity of FO model checkingon partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula h, and determines whether h holds on P in time f(h,w)n².

Based on joint work with Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, M. S. Ramanujan, and Saket Saurabh.

I will discuss new algorithms for a collection of related problems: random hypergraph partitioning (the hypergraph generalization of the stochastic block model), planted random k-SAT, and inverting Goldreich's one-way function. In each the goal is to find a planted solution at the lowest possible edge or clause density. I will present both positive algorithmic results and lower bounds for general classes of algorithms. Based on joint work with Vitaly Feldman, Santosh Vempala, and Laura Florescu.

In this talk, we will survey recent work on the computational complexity of binary constraint satisfaction problems (CSPs) that are not tractable only due to the structure of the instance (such as bounded treewidth) or the types of the constraints in the instance (such as linear equations).

A part of this talk is based on joint work with David Cohen, Martin Cooper, and Peter Jeavons.

The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE-complete to find the solution that is computed by the simplex method using Dantzig's pivot rule. Secondly, we prove that deciding whether Dantzig's rule ever chooses a specific variable to enter the basis is PSPACE-complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig's pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and show PSPACE-completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.

Joint work with John Fearnley

We study the behavior of random walk on dynamical percolation. In this model, the edges of a graph G are either open or closed, and refresh their status at rate \mu. At the same time a random walker moves on G at rate 1 but only along edges which are open. The regime of interest here is when \mu goes to zero as the number of vertices of G goes to infinity, since this creates long-range dependencies on the model. When G is the d-dimensional torus of side length n, we prove that in the subcritical regime, the mixing times is of order n^2/\mu. We also obtain results concerning mean squared displacement and hitting times.

This is a joint work with Yuval Peres and Jeff Steif.

A fundamental theorem of Wilson states that, for every graph F, every sufficiently large F-divisible clique has an F-decomposition. Here G has an F-decomposition if the edges of G can be covered by edge-disjoint copies of F (and F-divisibility is a trivial necessary condition for this). We extend Wilson’s theorem to graphs which are allowed to be far from complete (joint work with B. Barber, D. Kuhn, A. Lo).

I will also discuss some results and open problems on decompositions of dense graphs and hypergraphs into Hamilton cycles and perfect matchings.

A variety of practical optimization problems such as sensor placement, document summarization, and influence maximization can be formulated in terms of maximizing a non-decreasing submodular function. One simple, yet practically effective approach to this problem is the simple, standard greedy algorithm, which requires time Θ(n^2). Unfortunately, this makes it impractical for extremely large data sets.

In this talk, I will present a new distributed greedy algorithm, based on joint work with Rafael Barbosa, Alina Ene, and Huy Le Nguyen. Unlike previous distributed approaches, our algorithm leverages the power of randomization to attain a constant-factor approximation, independent of the number of machines used. Moreover, our results can be applied to general matroid constraints and knapsack constraints, as well as decreasing submodular functions.

Gyárfás conjectured in 1985 that if G is a graph with no induced cycle of odd length at least 5, then the chromatic number of G is bounded by a function of its clique number. We prove this conjecture, and discuss some further results. Joint work with Paul Seymour.

In the traditional model of algorithmically solving a game, the entire game is the "input data", which is presented in its entirety to an algorithm that is supposed to compute a solution, for example an exact/approximate Nash/correlated equilibrium. In some situations it may be preferable to regard the game as a "black box" which the algorithm can find out about via queries. For example, a complete description of a multi-player game may be infeasibly large. In this talk, we give an overview of recent work on algorithms that find game-theoretic equilibria via a sequence of queries that specify pure-strategy profiles, and answer with the associated payoffs. The main research issue is "query complexity", which refers to how many queries are needed in order to find a given kind of solution.

An n-vertex graph with no r-regular subgraphs are forests if r=2, thus it has at most n-1 edges. For r>=3, Pyber showed that it has at most c_rn log(n) edges for some c_r. For hypergraphs, Mubayi and Verstraete showed that n-vertex k-graphs with no 2-regular subgraphs has at most {n-1 choose k-1} edges if k>=4 is even and n is sufficiently large. In this talk, we prove that for every integer r>=3, an n-vertex k-graph H containing no r-regular subgraphs has at most (1+o(1)){n-1 choose k-1} edges if k>r and n is sufficiently large. Moreover, if r=3,4, r|k, and n, k are both sufficiently large, then the maximum number of edges in H is exactly {n-1 choose k-1}, with equality only if all edges contain a specific vertex v. We also ask some related questions.

Erdős and Sós proposed a problem of determining the maximum number F(n) of rainbow triangles in 3-edge-colored complete graphs on n vertices. They conjectured that F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd, where a+b+c+d=n and a,b,c,d are as equal as possible. We prove that the conjectured recurrence holds for sufficiently large n. We also prove the conjecture for n = 4^k for all k >= 0. These results imply that lim F(n)/{n choose 3}=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.

Joint work with József Balogh, Bernard Lidický, Florian Pfender, Jan Volec and Michael Young.

A generalized shifted graph is a graph whose vertices are ordered k-subsets a well ordered ground set and two vertices a_1<a_2<...<a_k and b_1<b_2<...<b_k are adjacent if they form some given pattern such as: a_1<a_2<b_1<a_3<b_2<...<b_k-2<a_k<b_k-1,<b_k. In the talk we study the behaviour of the chromatic number of such graphs. (This is a joint work with Christian Avart and Vojta Rödl.)

The Ramsey number r(K_s,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph on N vertices contains either a red n-dimensional hypercube Q_n, or a blue clique on s vertices. In 1983, Burr and Erdos conjectured that r(K_s,Q_n) = (s-1)(2^n - 1)+1 for every positive integer s and sufficiently large n. In this talk we shall sketch the proof of this conjecture and discuss some related problems. (Joint work with Gonzalo Fiz Pontiveros, Simon Griffiths, Rob Morris and David Saxton.)

Burr and Rosta conjectured that given any fixed (small) graph H, a random 2-colouring of the edges of the complete graph K_n contains (asymptotically) the minimum number of monochromatic copies of H. This conjecture was disproved by Sidorenko, who showed that it is false when H is a triangle with a pendant edge. Despite a number of other special cases having been resolved since, the general classification problem remains wide open. We explore an analogous question concerning monochromatic additive configurations contained in 2-colourings of the cyclic group Z_p and the finite-dimensional vector space F_p^n. (This is joint work with Alex Saad.)

We will discuss both integral and fractional versions of "correlated stable matching" problems. Each player is a node in a social network and strives to form a good match with a neighboring player; the player utilities from forming a match are correlated. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We especially focus on networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions.

When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly improves the quality of stable solutions. Furthermore, a good stable matching always exists and can be reached in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. Finally, we extend most of our results to network contribution games, in which players can decide how much effort to contribute to each incident edge, instead of simply choosing a single node to match with.

The large spectrum, the set of frequencies where the Fourier transform of a given set is particularly large, plays an important role in arithmetic combinatorics. A important result about such sets is Chang's lemma, which gives a sharp bound for the additive dimension of such sets, the size of the largest dissociated subset. We present a new structural lemma which, for certain applications, is a quantitative improvement of Chang's lemma. As an application, we discuss how this can be used to obtain a new quantitative result for Roth's theorem on three term arithmetic progressions.

In real-life multi-agent projects, agents often choose actions that are highly inefficient for the project or damaging for other agents because they care only about their own contracts and interests. We show that this can be avoided by the right project management. We model agents with private workflows including hidden actions and chance events, which can influence each other through publicly observable actions and events. We design an efficient mechanism for this model which is prior-free, incentive-compatible, collusion-resistant, individually rational and avoids free-riders.

Heinz Hopf asked if the sign of the (reduced) Euler characteristic of the nonpositively curved manifold is determined by its dimension. The question was motivated by the following strategy (for Riemannian met‐ ric). Is there a higher‐dimensional analogue of Gauß‐Bonnet formula? Is the integrand of constant sign? The answer to the first question is affirmative, but the second is not true. Thus the problem remains open. If the manifold carries piecewise Euclidean metric, the version of Gauß‐Bonnet formula is obvious. Even in the simplest case of cubbed manifold (i.e. a manifold made of cubes) the "integrand" becomes an in‐ teresting combinatorial quantity. According to extremely simple, though beautiful construction due to Mike Davis the second question is equivalent to the original Hopf question (for cubbed manifolds). In the talk we would discuss the connection between "no missing faces" triangulation of spheres and nonpositively curved cubbed manifolds. We would derive famous Charney‐Davis Conjecture (Hopf conjecture for cubbed manifolds) and discuss the up‐to‐date human knowledge about it (as well as hopes and illusions).

We consider problems where n people are communicating and a random subset of them is trying to leak information, without making it clear who are leaking the information. We introduce a measure of suspicion, and show that the amount of leaked information will always be bounded by the expected increase in suspicion, and that this bound is tight. Suppose a large number of people have some information they want to leak, but they want to ensure that after the communication, an observer will assign probability at most c to the events that each of them is trying to leak the information. How much information can they reliably leak, per person who is leaking? We show that the answer is -log(1−c)/c-log(e) bits.

We consider several problems where the goal is partition a ground set into several pieces while minimizing a "cut-type" objective function; examples include Multiway Cut, Node-weighted Multiway Cut, Metric Labeling and Hypergraph Labeling. A natural LP relaxation gives an optimal approximation for these problems, assuming the Unique Games Conjecture (the UGC assumption can be removed for certain submodular generalizations of these problems). However, we do not know how to round this LP in general and the focus has been on understanding this LP for specific problems. In this talk, we describe several rounding strategies and an integrality gap construction that leads to a simplex coloring conjecture reminiscent of Sperner’s Lemma.

This talk is based on joint work with Chandra Chekuri (UIUC), Huy Nguyen (Simons Institute Berkeley), Jan Vondrak (IBM Research Almaden), and Yi Wu (Google).

We consider the problem of evaluating positive equality-free sentences of FO on a fixed, finite relational structure B. This may be seen as a generalisation of the Quantified Constraint Satisfaction Problem (QCSP), itself a generalisation of the Constraint Satisfaction Problem (CSP). We argue that our generalisation is not totally arbitrary, and that ours is the only problem in a large class - other than the CSP and QCSP - whose complexity taxonomy was unsolved.

We introduce surjective hyper-endomorphisms in order to give a Galois connection that characterises definability in positive equality-free FO. Through the algebraic method we are able to characterise the complexity of our problem for all finite structures B. Specifically, the problem is either in Logspace, NP-complete, co-NP-complete or Pspace-complete.

The problem appears obtuse, but possesses a surprising elegance. There may yet be lessons to be learnt in the methodology of the solution of this case, for the continuing program for CSP.

Andrew Chester (Melbourne), Riccardo Dondi (Bergamo), Anthony Wirth (Melbourne) The Minimum Rooted Triplet Inconsistency (MinRTI) problem represents a key computational task in the construction of phylogenetic trees, whose goal is the reconstruction of a large tree that incorporates the information contained in a given set of triplets. Inspired by Aho et al's seminal paper and Bryant's thesis, we consider an edge-labelled multigraph problem, called Minimum Dissolving Graph (MinDG), and we show that is equivalent to MinRTI. We prove that on an n-vertex graph, for every x > 0, MinDG is hard to approximate within a factor in O(2^{\og^{1-x}n}), even on trees formed by multi-edges. Then, via a further reduction, this inapproximability result extends to MinRTI. In addition, we provide polynomial-time algorithms that return optimal solutions when the input multigraph is restricted to a multi-edge path or a simple tree. Finally, we investigate the complexity of MinRTI (and of MinDG) when the number of occurrences of every label is bounded, and we show that the problem is APX-hard when this bound is equal to five.

Let P be a fixed hereditary graph class. In the P Completion problem, given a graph G and an integer k, we ask whether it is possible to add at most k edges to G to obtain a member of P. In the recent years completion problems received significant attention from the perspective of parameterized complexity, with the standard parameterization by k. In my talk I will first survey the history of the study of parameterized complexity of completion problems, including the breakthrough paper of Villanger et al that settles fixed-parameter tractability of Interval Completion, as well as recent advancements on polynomial kernelization.
Then, we will move to the main topic of the talk, namely subexponential parameterized algorithms. First fixed-parameter algorithms for completion problems focused mostly on the ‘forbidden induced subgraphs’ definition of the graph class P in question. In 2012 Fomin and Villanger came up with a novel idea to instead focus on some structural definition of the class P, trying to build the modified output graph by dynamic programming. Slightly simplifying, we may say that the main technical contribution of Fomin and Villanger is a bound of at most exp(sqrt(k)log(k)) reasonable ‘partial chordal graphs’ for an input instance (G, k) of Chordal Completion. Consequently, Chordal Completion can be solved in exp(sqrt(k)log(k))+poly(n) time. Following the approach of Fomin and Villanger, in the past two years subexponential parameterized algorithms were shown for the class of chain, split, threshold, trivially perfect, pseudosplit and, very recently, proper interval and interval graphs. Moreover, a few lower bounds for related graph classes were found.
In my talk I will present the approach of Fomin and Villanger mostly on the example of Trivially Perfect Completion, and then survey the main ideas needed in the remaining algorithms.

Privacy preserving data publishing is an important problem that has been extensively studied in the past decades. The state-of-the-art solution to the problem is differential privacy, which offers a strong degree of privacy protection without relying on restrictive assumptions of the adversary. In this talk, we first give a brief introduction to differential privacy, then show how to handle the publication of high-dimensional sensitive data with differential privacy guarantees.

Szemerédi’s regularity lemma is one of the most powerful tools in graph theory. Roughly speaking, the lemma says that the vertex set of any graph may be partitioned into a small number of parts such that the bipartite subgraph between almost every pair of parts behaves in a random-like fashion. Addressing a question of Gowers, we determine the order of the tower height for the partition size in a version of Szemerédi’s regularity lemma.

Joint work with Jacob Fox.

The dimension of a poset P is the minimum number of linear extensions of P whose intersection is equal to P. This parameter plays a similar role for posets as the chromatic number does for graphs. A lot of research has been carried out in order to understand when and why the dimension is bounded. There are constructions of posets with height 2 (but very dense cover graphs) or with planar cover graphs (but unbounded height) that have unbounded dimension. Streib and Trotter proved in 2012 that posets with bounded height and with planar cover graphs have bounded dimension. Recently, Joret et al. proved that the dimension is bounded for posets with bounded height whose cover graphs have bounded tree-width. My current work generalizes both these results, showing that the dimension is bounded for posets of bounded height whose cover graphs exclude a fixed (topological) minor. The proof is based on the Robertson-Seymour and Grohe-Marx structural decomposition theorems.

In this talk, I will survey results relating the dimension of a poset to structural properties of its cover graph and present some ideas behind the proof of the result on excluded minors.

I will present a selection of open problems related to random walks on graphs that I hope will be of interest to the computer science and extremal combinatorics communities.

We prove the following conjecture of Heckman and Thomas: every triangle-free graph with maximum degree 3 is fractionally (14/5)-colorable. A graph is fractionally k-colorable if every vertex can be assigned a measurable subset of [0,k) of unit Lebesgue measure and the sets of every two adjacent vertices are disjoint.

This is a joint work with Zdeněk Dvořák and Jean-Sébastien Sereni.

An occurrence of the pattern p in a permutation Π is a subsequence of length |p| in Π whose letters appear in the same order of size as the letters in p. For example, the subsequence 425 in 341625 is an occurrence of 213, whereas 341625 avoids 321. The set of all finite permutations forms a poset with respect to pattern containment. As this poset embodies all pattern containment (and avoidance) in permutations, it is a fundamental object in all pattern studies. We study its intervals [A,B], that is, sets of permutations containing a given permutation A and contained in another permutation B. This poset has a rich structure, only a little of which is understood so far.

Any interval I has an associated simplicial complex, called its order complex, whose topological properties are closely connected to properties of I. For example, the reduced Euler characteristic of an order complex equals the Möbius function of the underlying poset. Thus, a boolean algebra, whose order complex is a sphere, has Möbius function ±1.

So far, we only know a few things about the topology and Möbius function of intervals in this poset. For example, we know that intervals of layered permutations (which are concatenations of decreasing sequences, each with smaller letters than the next, such as 321465) are shellable. That implies they are homotopy equivalent to wedges of spheres, and the Möbius function, which equals, up to a sign, the number of spheres, can be computed in polynomial time. The same is true for intervals of permutations with a fixed number of descents (pairs of adjacent letters in decreasing order). We can also compute, in polynomial time, the Möbius function for intervals of separable permutations (those avoiding 2413 and 3142) and we conjecture that they are also shellable.

I will report on joint work with Peter McNamara and work of my student Jason Smith.

In Diffusion Load Balancing one assumes that a set of m tasks are arbitrarily distributed over n resources. The system is modelled by a graph where the nodes represent the resources and the edges represent communication links between resources. Diffusion Load Balancing works in synchronous rounds. In every round every node is allowed to balance its load with its direct neighbours in the network. The later model is usually assumed to be the more realistic model. The question is not how long does it take to balance the load as evenly as possible.

One distinguishes between continuous and discrete models. In continuous load balancing the tasks can be split arbitrarily, allowing neighbouring nodes to balance their load evenly. In discrete load balancing tasks can not be split at all and a well balanced situation is much harder to achieve.

In this talk I will introduce two different frameworks that translate a continuous load balancing scheme into a discrete versions. The first scheme tries to simulate the continuous algorithm whereas the second scheme is a more direct approach.

We study a natural process for allocating m balls (tasks) into n bins (resources) that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first chooses a vertex u in G uniformly atrandom. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. In this talk we derive bounds on the maximum load of this process and the time until every bin has at least one ball allocated to it.

Many practical problems (e.g., signal and image processing) can be formulated as l₀-minimization problems, which seek the sparsest solution to an underdetermined linear system. The recent study indicates that l₁-minimization is efficient for solving l₀-problems in many situations. From a mathematical point of view, however, the understanding of the relationship between l₀- and l₁-minimization remains incomplete. Their relationship can be further interpreted via the property of the range space of the transpose of matrices, which provides an angle to completely characterize the uniqueness of l₁-minimizers and the uniform recovery of k-sparse signals. This analysis leads naturally to the concept of range space property (RSP) and the so-called 'full-column-rank' property, which altogether provide a broad understanding of the equivalence and the strong equivalence between l₀- and l₁-minimization problems.

Many decision problems can be cast as dynamic resource allocation problems, i.e., they can be framed in the context of a set of requests requiring a complex time-based interaction amongst a set of available resources. For instance scheduling, one of the classic problem in Operations Research, belongs to this class.

For this class of problem we present a new optimization framework. The framework a) allows modeling flexibility by incorporating different objective functions, alternative sets of resources and fairness controls; b) is widely applicable in a variety of problems in transportation, services and engineering; and c) is tractable, i.e., provides near optimal solutions fast for large-scale instances. To justify these assertions, we model and report encouraging computational results on three widely studied problems - the Air Traffic Flow Management, the Aircraft Maintenance Problems and Job Shop Scheduling. Finally, we provide several polyhedral results that offer insights on its effectiveness.

Joint work with D. Bertsimas and S. Gupta

Nonnegative matrix factorization (NMF) has become a widely used tool for analysis of high-dimensional data. In this talk, we first present a series of applications of NMF in image processing, text mining, and hyperspectral imaging. Then we address the problem of solving NMF, which is NP-hard in general. However, certain special cases, such as the case of separable data with noise, are known to be solvable in polynomial time. We propose a very fast successive projection algorithm for this case. Variants of this algorithm have appeared previously in the literature; our principal contribution is to prove that the algorithm is robust against noise and to formulate bounds on the noise tolerance. A second contribution is an analysis of a preconditioning strategy based on semidefinite programming that significantly improves the robustness against noise. We present computational results on artificial data and on a simulated hyperspectral imaging problem. (Joint work with Stephen Vavasis; see http://arxiv.org/abs/1208.1237 and http://arxiv.org/abs/1310.2273 for more details.)

We consider here Temporal Networks. They are defined by a labelling L assigning a set of discrete time-labels to each edge of the graph G of the network. The labels of an edge are natural numbers. They indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular we consider time-respecting paths , i.e. paths whose edges are assigned by L a strictly increasing sequence of labels. We begin by giving efficient algorithms for computing shortest time-respecting paths. We then prove a natural analog of Menger’s theorem holding for arbitrary temporal networks. Finally we propose two cost minimization parameters for temporal network design. One is the “temporality” of G , in which the goal is to minimize the maximum number of labels per edge and the other is the temporal cost of G , where the goal is to minimize the total number of labels used. Optimization of these parameters is subject to some connectivity constraints. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graphs like rings, trees, directed acyclic graphs. We also examine how hard is to compute (even approximately) such costs. This work is joint with G. Mertzios and O. Michail and appeared in ICALP 2013.

The generalized flow model is a classical extension of network flows. Besides the capacity constraints, there is a gain factor given on every arc, such that the flow amount gets multiplied by this factor while traversing the arc. Gain factors can be used to model physical changes such as leakage or theft. Other common applications use the nodes to represent different types of entities, e.g. different currencies, and the gain factors correspond to the exchange rates. We investigate the flow maximization problem in such networks. This is described by a linear program, however, no strongly polynomial algorithm was known before, despite a vast literature on combinatorial algorithms. From a general linear programming perspective, this is probably the simplest linear program where Tardos's general result on strongly polynomial algorithms does not apply. We give the first strongly polynomial algorithm for the problem. It uses a new variant of the classical scaling technique, called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted, reducing the size of the problem instance.

Let S be a sum of n independent integer random variables, each supported on {0,1,...,k−1}. How many samples are required to learn the distribution of S to high accuracy? In this talk I will show that the answer is completely independent of n, and moreover I will describe a computationally efficient algorithm which achieves this low sample complexity. More precisely, the algorithm learns any such S to ε-accuracy (with respect to the total variation distance) using poly(k,1/ε) samples, independent of n. Its running time is poly(k,1/ε) in the standard word RAM model.

This result a broad generalization of the main result of [Daskalakis, Diakonikolas, Servedio-STOC'12] which gave a similar learning result for the special case k=2 (when the distribution S is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k=2, sums of independent {0,1,2}-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated --- they are not log-concave, they can have Ω(n) local optima, there is no relationship between the Kolmogorov distance and the total variation distance for the class, etc.

The heart of the learning algorithm is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent {0,1,...,k−1}-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the constituent random variables in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent {0,1,...,k−1}-valued random variables, is of independent interest.

The talk will be based on a joint work with Costis Daskalakis, Ryan O'Donnell, Rocco Servedio and Li-Yang Tan.

In this talk, I shall discuss an approximation algorithm for {0,1}-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, given a {0,1}-edge-weighting of the complete graph Kn on n vertices, our algorithm outputs a Hamilton cycle H of Kn with the following property: the proportion of Hamilton cycles of Kn whose weight is smaller than that of H is at most n^-1/29 = o(1). Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio 1/2 - o(1) for arbitrary edge weights. On the hardness side we can show that, if the Exponential Time Hypothesis holds, there exists a constant C such that n^-1/29 cannot be replaced by exp(-(log n)^C) in the result above. (Joint work with Daniela Kühn and Deryk Osthus)

In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,...,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. Although there exists simple algorithm for solving file maintenance problem for more than 30 years (Itai, Konheim, Rodeh, 1981) no matching lower bound was known until our recent result (Bulanek, Koucky, Saks, STOC 2012). For the case m=n^C for C>1, there was known lower bound (Dietz, Seiferas, Zhang, 2004), however the proof was rather complicated and could not be extended to even bigger m (for example m=n^{log n}). This was solved in our next result (Babka, Bulanek, Cunat, Koucky, Saks, ESA 2013). In this talk I would like to talk about the importance of the Online Labeling for Cache oblivious algorithms and also I would like to show basic ideas of our results.

Joint work with Martin Babka, Vladimír Cunat, Michal Koucky, Michael Saks

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such 'local' modifications of the Erdös-Rényi random graph process has received considerable attention during the last decade, so far only rather simple rules are well understood. Indeed, the main focus has been on 'bounded-size' rules, where all component sizes larger than some constant B are treated the same way, and for more complex rules very few rigorous results are known.

We study Achlioptas processes given by (unbounded) size rules such as the sum and product rules. Using a variant of the neighbourhood exploration process and branching process arguments we show that certain key statistics are tightly concentrated at least until the susceptibility (the expected size of the component containing a randomly chosen vertex) diverges. Our convergence result is most likely best possible for certain rules: in the later evolution the number of vertices in small components may not be concentrated. Furthermore, we believe that for a large class of rules the critical time where the susceptibility 'blows up' coincides with the percolation threshold.

Joint work with Oliver Riordan.

We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the lp norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. The key idea of our novel method is to show that for goal functions that are sufficiently well-behaved functions of the machine loads, it is possible to compute in polynomial time a highly structured nearly optimal schedule. Monotone approximation schemes have an important role in the emerging area of algorithmic mechanism design. In the game-theoretical setting of these scheduling problems there is a social goal, which is one of the objective functions that we study. Each machine is controlled by a selfish single-parameter agent, where its private information is its cost of processing a unit sized job, which is also the inverse of the speed of its machine. Each agent wishes to maximize its own profit, defined as the payment it receives from the mechanism minus its cost for processing all jobs assigned to it, and places a bid which corresponds to its private information. For each one of the problems, we show that we can calculate payments that guarantee truthfulness in an efficient manner. Thus, there exists a dominant strategy where agents report their true speeds, and we show the existence of a truthful mechanism which can be implemented in polynomial time, where the social goal is approximated within a factor of 1+ε for every ε>0.

In recent time, there has been a lot of interest in balanced graph partitioning of large scale graphs to scale out computations that use as input a large-scale graph input data by running in parallel on distributed clusters of machines. Traditional balanced graph partitioning asks to partition a set of vertices such that the number of vertices across different partitions is balanced within some degree of slackness, and the number of cut edges is minimized. This problem is known to be NP hard and the best known approximation ratio is O(\sqrt{\log n \log k}) for partitioning of a graph with n vertices to k partitions. Substantial work was recently devoted to studying the online graph partitioning problem where vertices are required to be irrevocably assigned to partitions as they are observed in an input stream of vertices, mostly by studying various heuristics and developing some limited theoretical results. An alternative way to partition a graph that has emerged recently is so called edge partitioning, where instead, the set of edges is partitioned. The motivation for the latter strategy for partitioning a graph is that many real-world graphs exhibit a power-law degree sequence, so some portion of vertices have large degrees and allowing to assign the edges incident to high-degree vertices to different partitions may allow to achieve a good load balance and a small cut. The problem becomes even more challenging with the cut cost defined to account for the aggregation of messages that is allowed by many distributed computations. In this talk, we will present our work and results in the area.

Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, polylines, ellipsoids and even convex polyhedra. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their tree-width and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

Description trees were introduced by Cori, Jacquard and Schaeffer in 1997 to give a general framework for the recursive decompositions of several families of planar maps studied by Tutte in a series of papers in the 1960s. We are interested in two classes of planar maps which can be thought as connected planar graphs embedded in the plane or the sphere with a directed edge distinguished as the root. These classes are rooted non-separable (or, 2-connected) and bicubic planar maps, and the corresponding to them trees are called, respectively, β(1,0)-trees and β(0,1)-trees.

Using different ways to generate these trees we define two endofunctions on them that turned out to be involutions. These involutions are not only interesting in their own right, in particular, from counting fixed points point of view, but also they were used to obtain non-trivial equidistribution results on planar maps, certain pattern avoiding permutations, and objects counted by the Catalan numbers.

The results to be presented in this talk are obtained in a series of papers in collaboration with several researchers.

Cutting planes (cuts, for short), or inequalities satisfied by integral solutions of systems of linear inequalities, are important tools used in modern solvers for integer programming problems. In this talk we present theoretical and computational results on split cuts — studied by Cook, Kannan and Schrijver (1990), and related to Gomory mixed-integer cuts — and recent generalizations, namely multi-branch split cuts. In particular, we give the first pure cutting plane algorithm to solve mixed-integer programs based on multi-branch split cuts. We also show that there are mixed-integer programs with n+1 variables which are unsolvable by (n-1)-branch split cuts. In computational work, we consider a family of quadratic unconstrained boolean optimization problems recently used in tests on the DWave quantum computer and discuss how they can be solved using special families of split cuts in reasonable time.

This is joint work with Neil Dobbs, Oktay Gunluk, Tomasz Nowicki, Grzegorz Swirczsz and Marcos Goycoolea.

A system of linear equations is partition regular if, whenever the natural numbers are finitely coloured, it has a monochromatic solution. We could instead talk about partition regularity over the rational numbers, and if the system is finite then these notions coincide. What happens in the infinite case? Joint work with Neil Hindman and Imre Leader.

We consider a firm purchasing and processing a storable commodity in a volatile commodity price market. The firm has access to both a commodity spot market and an associated financial derivatives market. The purchased commodity serves as a raw material which is then processed into an end product with uncertain demand. The objective of the firm is to coordinate the replenishment and financial hedging decisions to maximize the mean-variance utility of its terminal wealth over a finite horizon.

We employ a dynamic programming approach to characterize the structure of optimal time-consistent policies for inventory and financial hedging decisions of the firm. Assuming unmet demand is lost, we show that under forward hedges the optimal inventory policy can be characterized by a myopic state-dependent base-stock level. The optimal hedging policy can be obtained by minimizing the variance of the hedging portfolio, the value of excess inventory and the profit-to-go as a function of future price. In the presence of a continuum of option strikes, we demonstrate how to construct custom exotic derivatives using forwards and options of all strikes to replicate the profit-to-go function. The financial hedging decisions are derived using the expected profit function evaluated under the optimal inventory policy. These results shed new light into the corporate risk and operations management strategies: inventory replenishment decisions can be separated from the financial hedging decisions as long as forwards are in place, and the dynamic inventory decision problem reduces to a sequence of myopic optimization problems. In contrast to previous results, our work implies that financial hedges do affect optimal operational policies, and inventory and financial hedges can be substitutes. Finally, we extend our analysis to the cases with backorders, price-sensitive demand, and variable transaction costs.

Joint work with Panos Kouvelis (Olin School of Business, Washington University in St. Louis, US) and Qing Ding (Huazhong University of Science and Technology, Wuhan, China.)

The Fast Fourier Transform (FFT) is one of the most fundamental numerical algorithms. It computes the Discrete Fourier Transform (DFT) of an n-dimensional signal in O(n log n) time. The algorithm plays an important role in many areas. It is not known whether its running time can be improved. However, in many applications, most of the Fourier coefficients of a signal are "small" or equal to zero, i.e., the output of the transform is (approximately) sparse. In this case, it is known that one can compute the set of non-zero coefficients faster than in O(n log n) time.

In this talk, I will describe a new set of efficient algorithms for the sparse Fourier Transform. One of the algorithms has the running time of O(k log n), where k is the number of non-zero Fourier coefficients of the signal. This improves over the runtime of the FFT for any k = o(n). If time allows, I will also describe some of the applications, to spectrum sensing and GPS locking, as well as mention a few outstanding open problems.

The talk will cover the material from the joint papers with Fadel Adib, Badih Ghazi, Haitham Hassanieh, Michael Kapralov, Dina Katabi, Eric Price and Lixin Shi. The papers are available at http://groups.csail.mit.edu/netmit/sFFT/

I will discuss prior-free profit-maximizing auctions for digital goods. In particular, I will give an overview of the area and I will focus on prior-free auctions with ordered bidders and identical items. In this model, we compare the expected revenue of an auction to the monotone price benchmark: the maximum revenue that can be obtained from a bid vector using prices that are non-increasing in the bidder ordering and bounded above by the second-highest bid. I will discuss an auction with constant-factor approximation guarantee for identical items, in both unlimited and limited supply settings. Consequently, this auction is simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have non-increasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next.

The central goal of compressed sensing is to capture attributes of a signal using very few measurements. In most work to date this broader objective is exemplified by the important special case of classification or reconstruction from a small number of linear measurements. In this talk we use information theory to derive fundamental limits on compressive classification, on the maximum number of classes that can be discriminated with low probability of error and on the tradeoff between the number of classes and the probability of misclassification. We also describe how to use information theory to guide the design of linear measurements by maximizing mutual information between the measurements and the statistics of the source.

In this talk, we consider some fundamental maximum throughput routing problems in directed graphs. In this setting, we are given a capacitated directed graph. We are also given source-destination pairs of nodes (s_1, t_1), (s_2, t_2), ..., (s_k, t_k). The goal is to select a largest subset of the pairs that are simultaneously routable subject to the capacities; a set of pairs is routable if there is a multicommodity flow for the pairs satisfying certain constraints that vary from problem to problem (e.g., integrality, unsplittability, edge or node capacities). Two well-studied optimization problems in this context are the Maximum Edge Disjoint Paths (MEDP) and the All-or-Nothing Flow (ANF) problem. In MEDP, a set of pairs is routable if the pairs can be connected using edge-disjoint paths. In ANF, a set of pairs is routable if there is a feasible multicommodity flow that fractionally routes one unit of flow from s_i to t_i for each routed pair (s_i, t_i).

MEDP and ANF are both NP-hard and their approximability has attracted substantial attention over the years. Over the last decade, several breakthrough results on both upper bounds and lower bounds have led to a much better understanding of these problems. At a high level, one can summarize this progress as follows. MEDP and ANF admit poly-logarithmic approximations in undirected graphs if one allows constant congestion, i.e., the routing violates the capacities by a constant factor. Moreover, these problems are hard to approximate within a poly-logarithmic factor in undirected graphs even if one allows constant congestion. In sharp contrast, both problems are hard to approximate to within a polynomial factor in directed graphs even if a constant congestion is allowed and the graph is acyclic.

In this talk, we focus on routing problems in directed graphs in the setting in which the demand pairs are symmetric: the input pairs are unordered and a pair s_i t_i is routed only if both the ordered pairs (s_i,t_i) and (t_i,s_i) are routed. Perhaps surprisingly, the symmetric setting can be much more tractable than the asymmetric setting. As we will see in this talk, when the demand pairs are symmetric, ANF admits a poly-logarithmic approximation with constant congestion. We will also touch upon some open questions related to MEDP in directed graphs with symmetric pairs.

This talk is based on joint work with Chandra Chekuri (UIUC).