The notion of treewidth and tree decompositions plays a central role in the study of graphs with forbidden minors. Besides structural characterizations, the property of having boundedtreewidth, or a tree decomposision with certain "nice" properties, can be used algorithmically. However, until very recently, there were very few results that allowed to analyze the treewidth of graphs that exclude certain induced subgraphs. Indeed, a large clique has large treewidth, but is H-free for any graph H which is not a clique. It turns out that some intresting relations between the two worlds can be found if we additionally put some restrictions on vertex degrees - either just by bounding the maximum degree, or, in some cases, by bounding the degeneracy.

During the talk we will discuss some results of this flavor. In particular, we will show that

• graphs of bounded degeneracy that exclude all cycles of length at least t have bounded treewidth;
• graphs of bounded degree that exclude a fixed subdivision of the claw admit a certain type of an "*induced* grid/wall theorem": they either contain the line graph of a big subdivided wall as an *induced subgraph*, or have bounded treewidth.

Based on the joint work with Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and with Abrishami, Chudnovsky, and Dibek.

The visibility graph of a polygon P is formed by the pairs of vertices u and v of P such that the segment uv is disjoint from the exterior of P. We show that the class of polygon visibility graphs is χ-bounded, thus answering a question by Kára, Pór, and Wood from 2005. Specifically, we prove the bound χ≤3⋅4^ω−1. We obtain the same bound for generalizations of polygon visibility graphs in which the polygon is replaced by a curve and straight-line segments are replaced by segments in a pseudo-line arrangement. The proof is carried through in the setting of ordered graphs. In particular, we show χ-boundedness of several classes of ordered graphs with excluded ordered substructures.

Joint work with James Davies, Tomasz Krawczyk, and Rose McCarty.

This is a part of Round the World Relay in Combinatorics organized by Oxford University.

Here is the full schedule: http://people.maths.ox.ac.uk/scott/relay.htm

And the zoom link for the whole event:

https://us02web.zoom.us/j/87593953555?pwd=UWl4eTVsanpEUHJDWFo3SWpNNWtxdz09

meeting id: 875 9395 3555
password: relay

Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to real-life scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.

We will overview the state-of-the-art results and techniques used in proofs of the lower bounds for constant depth circuits. We focus mostly on classes AC[0], ACC[0] and CC[0]. The most important challenges and some open problems are to be discussed.

In our paper [LICS'18] a generalization of Boolean circuits to arbitrary finite algebras was introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However nilpotent but not supernilpotent algebras have not been put on any side of this borderline.

This paper provides a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce Boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general.

Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy was shown by Bulatov and Zhuk.

Joint work with Piotr Kawałek and Jacek Krzaczkowski

Given an n-by-n generator matrix with entries being subsets of a fixed field we generate the set of all matrices with entries coming from the corresponding entries in the generator matrix. Such a set of matrices is strongly singular if each member is a singular matrix. In this talk I will survey natural generalizations and connections to other problems. In particular, I will describe algorithm by Geelen for  maximum rank matrix completion problem.

Given a graph class C, a graph G is universal for C if it "contains" all the graphs from C. As there are several notions of containment, there are several notions of universal graphs. In this talk I'll mention two versions:

• induced-universal graphs: here G contains all the graphs of C as induced subgraphs
• isometric-universal graphs: here G contains isometric copies of all the graphs from C (isometric means that the distances are preserved in the embedding)

Note that an isometric copy is an induced copy, so the second notion is stronger. These notions are closely related to the notion of labelling schemes in graphs. The goal is to assign labels to the vertices of each graph G from C such that upon reading the labels of any two vertices u and v, we know some properties of u and v in G (whether they are adjacent, or their distance, or whether u is reachable from v if G is a digraph). It turns out that minimizing the size of the labels is equivalent to constructing small universal graphs, at least in the case of induced-universal graphs. For isometric-universal graphs some additional work needs to be done.

I'll survey some recent progress in this area. In particular I'll show how to construct induced-universal graphs of almost optimal size for any hereditary class, using the regularity lemma. In particular this implies almost optimal reachabilty labelling schemes in digraphs and comparability labelling schemes in posets, and the construction of an almost optimal universal poset for the class of all n-element posets (of size 2^n/4+o(n)). I will also show how to construct isometric-universal graphs of size 3^n+o(n) for the class of all n-vertex graphs, answering a question of Peter Winkler.

Based on joint work with Marthe Bonamy, Cyril Gavoille, Carla Groenland, and Alex Scott.

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

We will discuss quasirandom properties of other combinatorial structures, tournaments, permutations and Latin squares in particular, and present several recent results obtained using analytic tools of the theory of combinatorial limits.

The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under

(i) inserting an element, and

(ii) deleting an element of an array.

In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/ϵ)^O(1/ϵ))-approximation of LIS under both operations with worst-case update time ~O(n^ϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains a (1+ϵ)-approximation of LIS under both operations with worst-case update time ~O(ϵ⁻⁵). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.

While this essentially settles the complexity of the approximate version of the problem, the exact version seems more elusive. The only known sublinear solution was given very recently by Kociumaka and Seddighin [STOC 2021] and takes ~O(n^2/3) time per update. We show polynomial conditional lower bounds for two natural extensions of this problem: weighted LIS and LIS in any subarray.

Joint work with Wojciech Janczewski

In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover graphs have bounded dimension. We generalise this result to posets with k-outerplanar cover graphs. Namely, we show that posets with k-outerplanar cover graph have dimension O(k³). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h³). This improves the previously best known bound of O(h⁶) by Kozik, Micek and Trotter.

Joint work with Maximilian Gorsky

https://arxiv.org/abs/2103.15920

We present a progress on local computation algorithms for two coloring of k-uniform hypergraphs. We focus on instances that (for a parameter α) satisfy strengthened assumption of Local Lemma of the form 2^1-αk(Δ+1)e<1, where Δ is the bound on the maximum edge degree of the hypergraph. We discuss how previous works on the subject can be used to obtain an algorithm that works in polylogarithmic time per query for α up to about 0.139. Then, we present a procedure that, within similar bounds on running time, solves wider range of instances by allowing α to be at most about 0.227.

Joint work with Jakub Kozik

Graph classes excluding a path or a subdivided claw as an induced subgraph are so far mysterious: on one hand, beside some corner cases, they do not seem to have any good structural description, but on the other hand, a number of combinatorial problems - including Maximum Independent Set (MIS) - lack an NP-hardness proof in these graph classes, indicating a possible hidden structure that can be used algorithmically. Furthermore, graphs excluding a fixed path as an induced subgraph were one of the earliest examples of a chi-bounded graph class, with an elegant proof technique dubbed the Gyarfas' path argument. In the recent years the progress accelerated, leading to, among other results, (a) a quasi-polynomial-time algorithm for MIS in graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the Erdos-Hajnal property in graph classes excluding a fixed forest and its complement. In the talk, I will survey these results, showing the role of the Gyarfas' path argument in most (all?) of them, and outline research directions for the future.

In this talk we survey results for pseudocircle arrangements. Along the way we present several open problems. Among others we plan to touch the following topics:

 * The taxonomy of classes of pseudocircle arrangements.
 * The facial structure with emphasis on triangles and digons.
 * Circularizability.
 * Coloring problems for pseudocircle arrangements.

The talk includes work of Grünbaum, Snoeyink, Pinchasi, Scheucher, myself, and others.

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t √ log t). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(k^c) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t'+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

Joint work with Carla Groenland, Gwenaël Joret, and Wojciech Nadara.

The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory and algorithmics. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs, a positive real ε and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B with |A|=Ω(n) and |B|=Ω(n^1-ε) such that in the d-th power of G, either there is no edge between A and B, or there are all possible edges between A and B.

The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(n^ω) time algorithms, for ω<2.373. On the other hand, the (min,+)-product, which is at the heart of APSP, is widely conjectured to require cubic time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems, e.g. the (min,max)-product, the min-witness product, APSP in directed unweighted graphs. The best runtimes for these "intermediate" problems are all O(n^(3+ω)/2). A similar phenomenon occurs for convolution problems.

Can one improve upon the running times for these intermediate problems? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way?

We make progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and min-witness product can be reduced to both the (min,max)-product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is equivalent to the famous 3SUM problem. As this variant is in O(n^3/2) time and 3SUM is in O(n²) time, our result gives the first fine-grained equivalence between natural problems of different running times.

Joint work with Andrea Lincoln and Virginia Vassilevska Williams.

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n⁴) time delay between the output of two consecutive graphs. We improve their algorithm and achieve O(n³ log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15 (previous best was 12).

The density D(G) of a graph G is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D(F) is the supremum of densities of graphs in F.

A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1,...,k. A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H. Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω(k^D(F)) and O(k^d), where d is the ceiling of D(F) (result obtained in 2015 with Gutowski), and has been conjectured to be ϴ(k^D(F)).

In this talk, I will present a construction of a k-universal graph on O(k^d) vertices for any rational bound d on the density D(F). It follows that if D(F) is rational, the minimum number of vertices in a k-universal graph for F is indeed ϴ(k^D(F)).

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω²) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n).

Joint work with Parinya Chalermsook.

A classic result of Erdős and Pósa (1965) states that for every graph G and every integer k, either G has k vertex-disjoint cycles, or G has a set of O(k log k) vertices meeting all cycles. The usual way of proving this theorem is through the so-called frame technique. In this talk I will describe another equally simple way of proving the theorem, using a ball packing argument. Then I will describe some applications of this method, including to the variant where only cycles of length at least l are considered.

Joint work with Henning Bruhn, Wouter Cames van Batenburg, and Arthur Ulmer.

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as Geometric k-Cut, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n⁴ log³ n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2−4/3k)-approximation algorithm.

Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

The Turán number ex(n, H) is the maximum number of edges that an H-free graph on n vertices can have. This quantity is well studied for graphs with chromatic number greater than 2, but the problem of determining it for all bipartite graphs remains open. A generalization of the Turán number, namely, the maximum possible number of copies of a graph T in an H-free graph on n vertices, denoted by ex(n, T, H), is recently attracting a lot of attention. In particular, the problem of determining ex(n, C₅, C₃), posed by Erdős in 1984, was completely solved in the last few years with the use of the flag algebras method.

In this talk, we will show an elementary proof that ex(n, C_k, C_k−2) = (n/k)^k + o(n^k) for any odd k > 5.

Joint work with Andrzej Grzesik.

Let 𝒞 and 𝒟 be hereditary graph classes. Consider the following problem: given a graph G ∈ 𝒟, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to 𝒞. We prove that it is solvable in 2^o(n) time, where n is the number of vertices of G, if the following conditions are satisfied:

• the graphs in 𝒞 are sparse, i.e., they have linearly many edges in terms of the number of vertices;
• the graphs in 𝒟 admit balanced separators of size governed by their density, e.g., O(Δ) or O(√m), where Δ and m denote the maximum degree and the number of edges, respectively; and
• the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph.

This leads, for example, to the following corollaries for specific classes 𝒞 and 𝒟:

• a largest induced forest in a P_t-free graph can be found in 2^Õ(n2/3) time, for every fixed t; and
• a largest induced planar graph in a string graph can be found in 2^Õ(n3/4) time.

Joint work with Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, and Erik Jan van Leeuwen.

Listing and counting triangles in sparse graphs are well-studied problems. For a graph with m edges, Björklund et al. gave an O(m^1.408) algorithm which can list up to m triangles. The exact exponent depends on the exponent omega in matrix multiplication, and becomes 4/3 if omega=2. Pătraşcu proved that an algorithm faster than O(m^4/3) would imply a sub-quadratic algorithm for 3-SUM, which is considered unlikely.

In our work we consider a variant of triangle problem asking to determine for every edge the number of triangles which contains that edge. We prove that this problem is no easier than listing up to m triangles, although it still admits an algorithm of the same O(m^1.408) complexity. We also propose a natural class of range query problems, including for example the following problem: given a family of ranges in an array, compute the number of inversions in each of them. We prove that all the problems in this class are equivalent, under one-to-polylog reductions, to counting triangles for each edge. In particular the time complexities of these problems are the same up to polylogarithmic factors.

This is joint work of Lech Duraj, Krzysztof Kleiner, Adam Polak and Virginia Vassilevska-Williams.

Graph colorings and online algorithms on graphs constitute the key fragments of the algorithmic graph theory. Specifically, the subject of this study will be a presentation of the results concerning

• different variants of coloring of graphs and partially ordered sets,
• online coloring of partially ordered sets,
• incremental matchings of bipartite graphs.

The first part of the talk will concern different aspects of the coloring problem as well as different evidential techniques. The presented results concern majority choosability of digraphs, harmonious coloring of hypergraphs and semi-uni conjecture of product of two posets. The next part of presentation will concern online chain partitioning of posets. There will be presented a full characterization of the class of posets, for which the number of colors (chains) used by first-fit is a function of width, i.e. best offline solution. This part will also present two different subexponential online algorithm for the online chain partitioning problem. The last part will concern the incremental matching problem in bipartite graphs. There will be presented an incremental algorithm that maintains the maximum size matching in total time equal the running time of one of the fastest offline maximum matching algorithm that was given by Hopcroft and Karp. Moreover, I will show an analysis of the shortest augmenting path algorithm.

This is joint work with Marcin Anholcer, Jarosław Grytczuk, Sebastian Czerwiński, Paweł Rzążewski, Stefan Felsner, Kolja Knauer, Grzegorz Matecki, Tomasz Krawczyk, H. A. Kierstead, Matthew Smith, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz.

A widely investigated subject in combinatorial geometry, originating from Erdős, is the following: given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances, e.g., determine the maximum number of unit distances, the maximum number of minimum/maximum distances, the minimum number of distinct distances? This has been generalized in many directions by taking point sets in a certain (not necessarily Euclidean) metric space and studying the distribution of certain configurations — and a whole theory emerged.

In this talk I propose the following problem variant: consider planar line arrangements of n lines, and determine the maximum number of unit/maximum/minimum area determined by these lines. We prove that the order of magnitude for the maximum occurrence of unit area lies between n² and n^2+1/4. This result is strongly connected to both additive combinatorial results and Szemerédi-Trotter type results. Next we show a tight bound for the maximum number of minimum area triangles. Finally we discuss a graph theoretic approach for the maximum number of maximum area triangles and present a recursive lower bound.

Joint work with Gábor Damásdi, Leo Martínez-Sandoval and Dániel T. Nagy.

We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by first-order expansions of countably infinite homogeneous graphs, that are, the structures first-order-definable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H.

Our main result is that structures under consideration have relational width exactly (2,L) where L is the maximal size of a forbidden subgraph in S, but not smaller than 3. It implies, in particular, that the CSP parametrized by such structures may be solved in time O(n^m) where n is the number of variables and m is the maximum of L and the arities of relations in the signature, while strict width l ensures time O(n^l+1). Furthermore, since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures, in which case, if finite, relational width is always at most (2,3). 

Finally, we show that certain maximally tractable constraint languages with a first-order definition in a countably infinite homogeneous graph whose CSPs are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, providing an alternative algorithm for already studied problems.

The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated longest common subsequence (LCS). For LCIS, as well as for LCS, there is an O(n²) algorithm and a SETH-based quadratic lower bound. Both the algorithm and the proof of the bound are, however, quite different for LCIS.

For LCS, there is also the Masek-Paterson O(n²/log n) algorithm. Its technique (the 'four Russians trick') does not seem to work for LCIS in any obvious way, so a natural question arises: does any sub-quadratic algorithm exist for Longest Common Increasing Subsequence problem?

We answer this question positively, presenting a O(n²/log^an) algorithm for some a>0. The algorithm is not based on memorizing small inputs (often used for logarithmic speedups, including LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.

Let G be a graph with maximum degree d. We show a randomized procedure that colors the edges of G so that:

• every two adjacent edges get two different color;
• edges of every cycle get at least three different colors.

Such a coloring is called an acylic edge-coloring of G. The minimum number of colors in an acyclic edge coloring of G is called the acylic index of G. It is conjectured that acylic index of G is at most d+2. We are able to prove that our coloring procedure succeeds for roughly 3.97d colors (improving on a previous result that used 4d colors).

This is joint work with Jakub Kozik and Xuding Zhu.

Gunrock is a CUDA library for graph-processing designed specifically for the GPU. It uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge.

Computational approach to the problem of solving equation, began with the question of David Hilbert. He asked, if there exists an algorithm, that decides wheather given Diophantine equation has a solution or not.  Yuri Matiyasevich proved this problem to be undecidable.  An analogy for decidability in finite realms is tractability. During the talk, we introduce the notion of PolSat problem for finite algebras and discuss the results for the wide class of algebraic structures.

We show that every 3-connected graph which contains many disjoint 2xn-grid minors, contains a 2x(n+1)-grid-minor. We use this result in a qualitative structure theorem for graphs without large 2xn grids.

This is a result from a joint paper with Tony Huynh, Gwenaël Joret, Piotr Micek and Paul Wollan

The class of unit interval graphs has at least 3 equivalent definitions:

• intersection graphs of unit-length intervals,
• intersection graphs of intervals such that no interval properly contains any other interval,
• K_1,3-free chordal graphs.

We ask whether the competitive ratio in the online unit-interval graph coloring with bandwidths depends on the chosen graph representation.

Based on the paper
Induced subgraphs of graphs with large chromatic number. III. Long holes
by Maria Chudnovsky, Alex Scott and Paul Seymour

a proof of a 1985 conjecture of Gyarfas that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ

will be presented.

We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.

Solving equations  is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider  equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is  obviously decidable in nondeterministic polynomial time.

The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on  the polynomial  equivalence problem in which we ask whether two polynomials over  a finite algebra describe the same function.

This is joint work with Paweł M. Idziak and Piotr Kawałek..

For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of {1, …, n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k + 1, k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥ 3, the odd graph K(2k + 1, k) has a Hamilton cycle. Its construction is based on constructing a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, it provides an alternative proof of the so-called middle levels theorem, originally proved by Mütze in 2014.

Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636).

We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor.

This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound.

The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].

Based on the paper:

Online bipartite matching with amortized O(log²n) replacements

In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points.  On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies.  On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization.

We propose a new efficient method that interpolates between these two approaches.  Our procedure strengthens any convex set containing a set of 0/1-points S, by exploiting certain additional information about S.  Namely, the required extra information will be in the form of a Boolean formula defining the target set S.  The strengthened relaxation is obtained by ''feeding'' the convex set into the formula defining S.
As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.

This is joint work with Samuel Fiorini and Stefan Weltge.

• Conditional lower bounds for k-mismatch pattern matching
• Faster algorithms for subset sum
• Complexity of 3-coloring for graphs with excluded k-paths

On-line interval coloring was studied by Kierstead and Trotter. They presented an algorithm with competitive ratio 3,and showed a construction which implies that there is no algorithm with competitive ratio strictly less than 3. However, their construction in asymptotic case requires intervals with possibly unbounded length.

We are interested in a variant of the on-line interval coloring problem in which all intervals have lenght between 1 and L. We show that as L tends to infinity the asymptotic competitive ratio tends to 5/2. Moreover we show that for L=1+epsi there is no algorithm with competitive ratio less than 5/3 and for L=2+epsi there is no algotihm with competitive ratio less than 7/4.

Finally, we want to know how the asymptotic competitive ratio changes as a function of L.

The purpose of my talk is to discuss several problems related to coloring and construction of appropriate representation for partially ordered sets (also posets) and graph classes derived from posets. In these problems, we will assume the following two scenarios:

in the first scenario, an algorithm receives a poset element one after another. For each new element added, the algorithm takes an irrevocable decision (assigns a color or extends a current representation) just after this element is presented (algorithms that work under such conditions are called on-line).

in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs.

In the context of on-line algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of on-line coloring of incomparability graphs, and embedding posets into d-dimentional space R^d.

In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs.

We focus our attention on:

• function graphs that are intersection graphs of continuous functions [0,1] → R,

• permutation graphs that are intersection graphs of linear functions [0,1] → R,

• trapezoid graphs that are intersection graphs of trapezoids spanned between two fixed parallel lines containing the bases of these trapezoids.

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound.

The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasipolynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.

Based on the paper:
Succinct progress measures for solving parity games,
by Marcin Jurdziński and Ranko Lazić

This study arises from the following question: what is the proportion of tautologies of the given length n among the number of all FO relational sentences of length n? We investigate the simplest language with a fixed signature σ = {r}, where r is a binary relation symbol. The model with four logic symbols and an universal quantifier lead us to discover an unexpected result - the fraction of valid sentences is always greater than a fixed constant and therefore the density, if exists, is positive. The main theorem is derived from the analysis of structural properties of FO formulae, which themselves bear strict resemblance to structural properties of λ-terms.

We propose a Ramsey theory for binary trees and prove that for every r-coloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have tree-chromatic number at most 2 while the path-chromatic number is bounded. This construction resolves a problem posed by Seymour.

Joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter.

Motivated by a connection to vertex-distinguishing colorings, we initiate the study of a new graph covering parameters: The k-strong induced arboricity. For a graph G and a positive integer k, a k-strong induced forest F in G is an induced forest in which every component has at least k edges. An edge in G is called k-valid if it is contained in at least one k-strong induced forest. The k-strong induced arboricity f_k(G) is the smallest number m such that all k-valid edges of G can be covered with m k-strong induced forests in G.

We demonstrate that the k-strong induced arboricity is not monotone, neither in k, nor under taking subgraphs or even induced subgraphs. In particular we construct 2-degenerate graphs G with f_k(G)≤ 3 and f_k+1(G) arbitrarily large. Focusing on the supremum f_k(C) of f_k(G) among all graphs G from a given graph class C, we prove that f_k(G) is finite whenever C is of bounded expansion. For the class C of planar graphs we prove that f_k(C) is 8,9 or 10. Moreover we give necessary and sufficient conditions for f₁(C) to be finite in terms of r-shallow minors of graphs in C, a notion recently introduced by Nešetřil and Ossona de Mendez.

This is based on joint work with Maria Axenovich, Philip Dörr, Daniel Gonçalves, and Jonathan Rollin.

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

1) A induces a subgraph of G of treewidth O(√k log k), and

2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2^{O(√k log2 k)}n^O(1))⁻¹, where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2^{O(√k log2 k)}n^O(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Michał Pilipczuk, and Saket Saurabh: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778.

The Longest Common Increasing Subsequence problem is a variant of classic Longest Common Subsequence problem, which can be solved in quadratic time with a simple dynamic programming algorithm. During the talk we will show a reduction from the Orthogonal Vectors problem to the Longest Common Increasing Subsequence problem which proves that the latter cannot be solved in strongly subquadratic time unless the SETH is false.

Simple modifications of the reduction prove that the problem for k sequences cannot be solved in O(n^k-ε) time, that the same lower bounds apply to the Longest Common Weakly Increasing Subsequence, and that the assumption of SETH can be replaced with a weaker statement about satisfiability of non-deterministic branching programs.

We study a class of graphs that have a special geometric representation. By a bar visibility representation of an undirected graph we mean a function that associates with each vertex of a graph a horizontal line segment in such a way, that between segments representing two ends of an edge there is a vertical strip (of visibility). In case of directed graphs, we additionally assume that the visibility is from the bottom to the top, that is the line segment representing the source of the edge is below the one for the target.

Graphs admitting such representations are well understood and can be recognized in linear time, both in the undirected and in the directed case. We work in a more subtle setting, where line segments are already associated with some vertices of a graph, and the question is if this can be extended to a bar visibility representation of an entire graph. We prove some results on complexity of this kind of problems.

This is joint work with Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk and Giuseppe Liotta. The manuscript is available here: https://arxiv.org/abs/1512.00174

 
A typical language translator uses a parser to convert an input string into some internal representation, usually in a form of an AST. The AST is then analyzed and transformed in passes. In the final pass, the AST is converted into the output, be it a machine code or source code of another language.
 
However, if we try to combine different languages, e.g. for a purpose of a multi-domain project, we may have a problem: each language uses different kinds of AST nodes, has different assumptions on the AST structure and features different pass algorithms. Settling for the common ground by limiting the node types, assumptions, and algorithms limits how the languages may reason about their code. Any high-level information is lost in such representation and high-level transformations cannot be defined.
 
Working on the common AST is similar to unstructured programming: AST acts as a global machine state. Any change to the state, e.g. introduced by a new language, may inadvertely affect the behavior of the existing languages. In regular programming we have moved away from unstructured programming towards higher abstraction levels, e.g. through functional programming. If it can be done to regular programming, can it be done to AST and code builders as well?
 
Our solution treats AST nodes not as objects of a fixed type. Instead, it is a function with its body describing entirely the behavior of such node. Even the connection between the nodes is represented internally by the function, in a form of continuations. 
The passes over the AST are replaced by a single invocation of these functions. The node functions may contain code for multiple stages of code analysis. In order to reduce the run time these additional stages are scheduled through dynamic staging.
 
This gives the power of abstraction to code building. Even nodes come from different languages may interact, as long as they understand the passed arguments.
 
This major change on how a code is represented requires changes in how we think about common basic operations during language interpretation:
- how do we link two nodes/functions together?
- how do we create control flow structures?
- how do we perform name lookups, even across different languages?
- how do we optimize the code so that the AST layer dissapears when generating code?
- what language-specific optimizations can be performed and how do we specify them?
 
We will address these questions in the upcoming talk.

1. S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colourings of Digraphs, Arxiv.
2. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk Every digraph is majority 4-choosable, Arixv.

• Online Deadline Scheduling with Machine Augmentation
• Scheduling with Precedence Constraints
• Multiway Cut
• Traveling Repairman Problem

In general, Hamiltonian Cycle Problem is NP-complete in triangular and square grids. In "Not being(super)thin or solid is hard: A study of grid Hamiltonicity" Arkin et al. claimed HCP for thin triangular grids and thin square grids to be NP-complete as well. However the arguments they gave are incorrect. In fact we show that thin triangular grids as well as thin square grids always have HC. Moreover we show a linear algorithm for finding a HC in such graphs.

We show that the edges of any triangulation of a closed surface different from the projective plane and the sphere can be oriented such that every vertex has non-zero outdegree divisble by three. This confirms a conjecture of Barát and Thomassen. We will explain why this is a first step towards the generalization of Schynyder woods from the plane to orientable surfaces and what is know
about this problem.

We study the maximum guaranteed size of a dimension two subposet of an n-element poset. A trivial lower bound of the order of n^{1/2} follows from the Dilworth's theorem. We show an upper bound of the order of n^{2/3} improving the n^{0.8295} result by Reiniger and Yeager. We also discuss promising methods for achieving a better lower bound.

We present a solution to problem arising in public transport routing systems:
How to efficiently obtain several diverse transit routes given a single-shortest-path solver together with graph representation of transport network.
The input contains desired number of results, not departure time range length which may be unknown even roughly.
We assume optimisation of both travel time and amount of penalties.

Based on public transport routing engine developed (2012-2013) in Teroplan S.A. (e-podróżnik.pl)

Solving linear systems of equations is a necessary step in numerical methods such as the Finite Element Method and Finite Difference Method. A variety of algorithms has been developed over the years including direct and indirect methods. In this work I want to present an direct multifrontal solver algorithm for special cases of systems coming from  h-adaptive two and three dimensional meshes. The solver algorithm is expressed through graph grammar productions and takes the advantage of advanced parallelization platform Galois.

based on the paper:

Damian Goika, Konrad Jopeka, Maciej Paszyńskia, Andrew Lenhartha, Donald Nguyenb and Keshav Pingalib,
Graph Grammar based Multi-thread Multi-frontal Direct Solver with Galois Scheduler,
doi:10.1016/j.procs.2014.05.086

Motivated by quite recent research involving the relationship between the dimension of a poset and graph theoretic properties of its cover graph, we show that for every $d\ge 1$, if $P$ is a poset and the dimension of a subposet $B$ of $P$ is at most~$d$ whenever the cover graph of $B$ is a block of the cover graph of $P$, then the dimension of $P$ is at most $d+2$.  We also construct examples which show that this inequality is best possible.
We consider the proof of the upper bound to be fairly elegant and relatively compact.  However, we know of no simple proof for the lower bound, and our argument requires a powerful tool known as the Product Ramsey Theorem.  As a consequence, our constructions involve posets of enormous size.

This is joint work with Bartosz Walczak and Ruidong Wang.

We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms
of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes.

Based on the paper:

On Exact Quantum Query Complexity, by Ashley Montanaro, Richard Jozsa and Graeme Mitchison

We investigate the behavior of data structures when the input and operations
are generated by an event graph. This model is inspired by Markov chains.
We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete, and query. The algorithm responds to the requests as it encounters them during a (random or adversarial) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal.

Based on the paper:

Data Structures on Event Graphs, by Bernard Chazelle and Wolfgang Mulzer

We examine the problem of determining a spanning tree of a given graph
such that the number of internal nodes is maximum. The best approximation algorithm known so far for this problem is due to Prieto and Sloper and has a ratio of 2. For graphs without pendant nodes, Salamon has lowered this factor to 7/4 by means of local search. However, the approximative behaviour of his algorithm on general graphs has remained open. In this paper we show that a simplified and faster version of Salamon's algorithm yields a 5/3-approximation even on general graphs. In addition to this, we investigate a node weighted variant of the problem for which Salamon achieved a ratio of 2·Δ(G)−3. Extending Salamon's approach we obtain a factor of 3+epsi for any epsi>0. We complement our results with worst case instances showing that our analyses are tight.

Based on the paper:

Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem, by Martin Knauer and Joachim Spoerhase

A new approach to the minimum-cost integral flow problem for small values of the flow is presented. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(k log(kn) + log²(kn)) time and using 2^k(kn)^O(1) processors. Thus, in particular, for the minimum-cost flow of value O(log n), we obtain an RNC² algorithm, improving upon time complexity of earlier NC and RNC algorithms.

Based on the paper:

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows, by Andrzej Lingas and Mia Persson

We prove that given a bipartite graph G with vertex set V and an integer k,
deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class Σ^p₂

Based on the paper:

Hitting All Maximal Independent Sets of a Bipartite, by Jean Cardinal and Gwenaël Joret

A probabilistically checkable proof (PCP) enables, e.g., checking the satisfiability of a 3-SAT formula ɸ, while only examining a constant number of locations in the proof. A long line of research led to the construction of PCPs with length that is quasi-linear in n := |ɸ|.

In a zero knowledge PCP with knowledge bound K, reading any K symbols of the proof reveals no additional information besides the validity of the statement; e.g., no information is revealed about the assignment satisfying ɸ. Kilian, Petrank, and Tardos gave a transformation from any PCP into a ZK-PCP with knowledge bound K, for any desired K. A drawback of their transformation is that it requires multiplying the proof length by a factor of (at least) K^6.

In this work, we show how to construct PCPs that are zero knowledge for knowledge bound K and of length quasilinear in K and n, provided that the prover is forced to write the proof in two rounds. In this model, which we call duplex PCP (DPCP), the verifier gets an oracle string from the prover, then replies with some randomness, and then gets another oracle string from the prover, and it can make up to K queries to both oracles.

Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but rely on algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure (which many constructions have, including [BFLS91,ALMSS98,BS08]) we can add the zero knowledge property at virtually no cost while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.

In this talk I will explain this notion. Then, to illustrate its usefulness, I will show how it was used by Fomin, Lokshtanov and Saurabh to design a fast algorithm for finding long simple paths in a directed graph.

Finally, I will describe a recent work where we generalize the notion of a representative set to a family of multisets and derive algorithmic applications.

Based on the paper Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints with Daniel Lokshtanov and Michał Pilipczuk

We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t_q=1+Θ(α/b) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547558, 2011) achieves t_q=1+1/2^Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Note that the two conditions hold on a real machine, although they are not stated in the cacheoblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t_q=1+O(α/b), which is exactly what linear probing achieves.  

An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA'07, pp.179188, SIAM, Philadelphia 2007) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs.

In this paper we treat the case of non-zero transmission cost c.We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected cost Θ(n+c·log n) and is in o(1)-equilibrium, where n is the number of users.  

In our talk we present our approach to solve these problems, by introducing a new metamorphic language - AnyDSL. The parsing and execution of AnyDSL can be interleaved and the latter can influence the former - e.g. by introducing a new grammar with which parsing should resume. Regardless of the language the source is written in, all code is translated into a low-level, functional representation in continuous passing style (AIR). AIR serves as a "meeting point", permitting inter-DSL communication. AIR can be interpreted or compiled to LLVM bytecode and then to machine code.

New grammars are defined also within AnyDSL. Unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies. With it the overhead of having multiple layers of languages can be resolved early. It also allows the DSL designer to specify domain specific optimizations. After all those transformations, AIR can be compiled to machine code that is efficient, with performance comparable to programs written in general-purpose languages.

In our talk we present a new metamorphic language - AnyDSL. AnyDSL permits the native parser to be exchanged with a custom DSL. Regardless of the DSL however, all code is translated into a low-level, functional representation in continuous passing style (AIR).

New grammars are defined also within AnyDSL, but unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies to resolve overheads and define domain specific optimizations. AIR can be compiled to machine code, and produced programs have performance comparable to those produced by general-purpose languages.  

We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^{4/7}). The previous best lower bound (shown by Buhrman et al. using information theoretic arguments) was Ω(√m). The same lower bound applies for larger sets using standard padding arguments. This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.

We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(√m) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets.  

List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.  

Our results are applicable to a more general problem, called Item Collection, in which only the relative order between packets' deadlines is known. REMIX is the optimal memoryless randomized algorithm against adaptive adversary for that problem  

We show that the k-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate within n^c, for any constant c<1.

If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1+ε, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log^{3/2}(n)/ε^2) [Andreev and Räcke in Theory Comput. Syst. 39(6):929–939, 2006] to O(log n). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of ε.  

BDD is equivalent to Positive First Order rewritability -- the very useful property that allows us to use (all the optimizations of) DBMS in order to compute the certain answers to queries in the presence of a theory.

Finite Controllability of a theory T means that if the certain answer to a query Q, for a database instance D , in the presence of T is 'no' then this 'no' is never a result of an unnatural assumption that the counterexample can be infinite.

We conjecture that for any theory T the property BDD implies FC. We prove this conjecture for the case of binary signatures.  

But does this mean that the question of the Continuum Hypothesis has no answer? Any "solution" must involve the adoption of new principles but which principles should one adopt? Alternatively, perhaps the correct assessment of Cohen's discovery is that the entire enterprise of the mathematical study of Infinity is ultimately doomed because the entire subject is simply a human fiction without any true foundation. In this case, any "solution" to the Continuum Hypothesis is just an arbitrary (human) choice.

Over the last few years a scenario has emerged by which with the addition of a single new principle not only can the problem of the Continuum Hypothesis be resolved, but so can all of the other problems  which Cohen's method has been used to show are also unsolvable (and there have been many such problems).  Moreover the extension of the basic (ZFC) principles by this new principle would be seen as an absolutely compelling option based on the fundamental intuitions on which the entire mathematical conception of Infinity is founded.

However, this scenario critically depends upon the outcome of a single conjecture. If this conjecture is false then the entire approach, which is the culmination of nearly 50 years of research, fails or at the very least  has to be significantly revised.

Thus the mathematical study of Infinity has arguably reached a tipping point. But which way will it tip?  

The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing x^*/2 in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in Fscr_{>0} into an s-t--path (or more generally, into a T-join) and its complement, which induces a decomposition of x^*. This decomposition can be refined and then efficiently used to complete x^*/2 without using linear programming or particular properties of T, but by adding to each cut deficient for x^*/2 an individually tailored explicitly given vector, inherent in the problem.

A simple example shows that the Best of Many Christofides algorithm may not find a shorter s-t--tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.  

We give an O(log^2 k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log^3 k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA'06). It is known that for this problem no deterministic algorithm can have a competitive better than 2k−1, and that no randomized algorithm can have a competitive ratio better than ln k.  

We first settle the problem complexity if unit size jobs have to be scheduled. More specifically, we devise a polynomial time algorithm for jobs with agreeable deadlines and prove NP-hardness results if jobs have arbitrary deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee. Additionally, we study problem settings where jobs have arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies.  

Kuznetsov and Tsybakov showed there are schemes where a message of length (1-p-o(1))*n can be encoded. We give the first such explicit schemes.

Our schemes follow from a construction of an object called an `invertible zero-error disperser'.

Joint work with Ronen Shaltiel.

It is known that all greedy algorithms solving this roblems use at least two times more cliques in the worst scenario than it is necessary in the optimal off-line solution. We introduce non-greedy approach, which leads us to construction of new better algorithms.

We start with connected graphs presented in a connected way with their proper interval representations. For this case we show an algorithm using at worst 8/5 times more cliques than it is needed. Later, we generalize this solution to the case of non-connected graphs. This time, we obtain an algorithm using at worst 13/8 times more cliques than it is necessary. We also generalize both algorithms to work without interval representation. Finally, we move towards unit interval representation and present an algorithm using at most 8/5 times more cliques than needed.

The performance of the algorithms is the best possible.

We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V|, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes W[1]-hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.  

We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number.We prove stronger algorithmic meta-theorems for these more restricted classes of graphs.More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.''  

For any two posets P and Q the size of a maximum semiantichain and the size of minimum unichain covering in the product PxQ are equal.

Here, semiantichain means a set for which each two points are not in a common unichain. B.Bosek, S.Felsner, K.Knauer and G.Matecki found conditions on P and Q that imply the conjecture in case of several new classes of posets. However, they also found an example showing that in general this min-max relation is false. This finally disproofs 30 year old conjecture of M.Saks and D.West.
 

We repeatedly grow an initial matching using augmenting paths up to a length of 2k+1 for k=2/ε. We terminate when the number of augmenting paths found in one iteration falls below a certain threshold also depending on k, that guarantees a 1+ε approximation. The main challenge is to find those augmenting paths without requiring an excessive number of passes. In each iteration, using multiple passes, we grow a set of alternating paths in parallel, considering each edge as a possible extension as it comes along in the stream. Backtracking is used on paths that fail to grow any further. Crucial are the so-called position limits: when a matching edge is the i-th matching edge in a path and it is then removed by backtracking, it will only be inserted into a path again at a position strictly lesser than i. This rule strikes a balance between terminating quickly on the one hand and giving the procedure enough freedom on the other hand.  

Traditional methods of automatic collection of unreachable objects (garbage) employ reference counting and/or graph traversal. The disadvantage of the former is its inherent inability to collect cyclic garbage structures (to deal with those, a supplemental, traversal-based method is often used). The latter suffers from having to traverse (at least periodically) all reachable objects. Heuristics based on the generational hypothesis lower this overhead, but only at the cost of failing to provide strong bounds on when garbage is going to be collected or how much total memory will be used. We propose a different approach, based on counting references between (approximations of) the strongly connected components of the object graph. Our method is real-time (has a constant time bound on any single operation), and concurrent (allows to interleave collection with program's activity). It provides an arbitrarily strong bound on memory usage. It makes use of the generational hypothesis, avoiding the traversal of objects permanently reachable by "old enough" edges. It uses constant memory per managed object plus constant global memory, and employs no data structures more complex than a stack, which gives hope that it can be performed in a lock-free manner.  

Finite spaces satisfying the T0 separability axiom may be easily identified with partially ordered sets, and the deformations of Stong turn out to be dismantlings by irreducible points. Some, natural from a topologist's point of view, generalizations of irreducible points give interesting definitions of "homotopy".

I will present relations between these notions and their connections to topics such as poset fixed point theory, evasiveness and homotopy theory of polyhedra.  

Most common framework for modeling probabilistic processes are Markov Chains, both discrete and continuos time and Markov Decision Processes. One of interesting questions one can ask about DTMCs and CTMCs is 'to what distribution given chain converges' (what's the steady state of it).

Theory of Markov Chains has over 100 years now and analytic solutions of all interesting questions are well known. Problem with such solutions is that they're usually untraceable for real-life models, because of their size. This is the reason why iterative methods are most commonly used. Unfortunately they also fail for some examples.

I'll show an algorithm which was proposed by Pokarowski in his PhD thesis and implemented by me just recently, which for some class of models gives huge speedup in return for some precision. I'll describe theory behind this algorithm, show how it works in general and some test results. I'll also tell what modifications are on the way and what we hope to achieve in the end.  

For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of randomized geometric partitioning.  

The problem has been posed by Felsner and Krawczyk in February 2010. Since then several groups have been trying hard to solve it, with only little success. The conjecture is trivial for w=1,2. I will present the proof for w=3. It is not clear whether it brings us closer to the proof of the general conjecture, but it seems promising. For w≥4 the question is open. Solving the problem for general w might give us some new insights into posets and Sperner theory.  

This is a joint work with Bartłomiej Bosek and Tomasz Krawczyk.  

The talk describes a construction of a universal countable graph, different from the Rado graph, such that for any of its vertices both the neighbourhood and the non-neighbourhood induce subgraphs isomorphic to the whole graph. This solves an open problem posed by A. Bonato at 18th BCC
 

We propose the following modification of an on-line matching. The algorithm matches each incoming vertex u in U to a set S(u) of adjacent vertices in V (instead of one vertex). In case when S(u) and S(x) for already existing x in U are not disjoint the algorithm must remove all common vertices from S(x). Additionally, the algorithm has to obey the rule: each S(x) must not become empty if only it was initialized with a nonempty set of vertices. An algorithm satisfying the above condition is called adaptive. In this approach a vertex u in U can be always matched to a vertex from S(u) (if S(u) is not empty). Therefore, the number of matched edges is equal to the number of nonempty sets S(u).

We are going to present the optimal adaptive on-line algorithm which breaks n/2 barrier and matches at least 0.589n+o(n) edges.  

An on-line chain partitioning algorithm receives the elements of a poset, point by point, from some externally determined list. When a new point is presented the algorithm learns its comparability status with previously presented points and makes an irrevocable choice of a color, keeping the invariant that all points with the same color form a chain. The choice of a color is made without knowledge of future points. The number of colors used by an on-line algorithm is usually compared to the width w of the poset. Kierstead showed that there exists an on-line algorithm that covers any poset with (5^w-1)/4 chains. On the other hand Szemeredi proved that any on-line algorithm for the on-line chain partitioning problem has to use at least (w^2+w)/2 colors. We reduce the huge gap between the exponential upper bound and the polynomial lower bound by improving the upper bound to the subexponential function: in fact we show an on-line chain partitioning algorithm that uses at most w^O(log w) many colors.  

However, neither Mazurkiewicz traces nor partial orders can effectively model more complex relationships, e.g., "not later than". In this talk, I will introduce the theory of generalized combined traces (generalized comtraces). Generalized comtraces are generalizations of Mazurkiewicz traces, where generalized stratified order structures are used instead of partial orders. This allows us to model even the most general case of concurrent behaviors under the assumption that observations are stratified orders. The theory of generalized comtraces also provides us a wide variety of new and interesting problems to work on.  

Let E_n be the set of all equations of the form
x_i = 1, or
x_i + x_j = x_k, or
x_i * x_j = x_k,
where i,j,k range over {1,...,n}. Moreover let K be one of the rings Z,Q,R,C. We construct a system S of equations from E_{21} such that S has infinitely many integer solutions and S has no integer solution in the cube [-2^{2^{21-1}},2^{2^{21-1}}]^{21}. We conjecture that if a system S, contained in E_n, has a finite number of solutions in K, then each such solution (x_1,...,x_n) satisfies (|x_1|,...,|x_n|) \in [0,2^{2^{n-1}}]^n. Applying this conjecture for K=Z, we prove that if a Diophantine equation has only finitely many integer (rational) solutions, then these solutions can be algorithmically found. On the other hand, an affirmative answer to the famous open problem whether each listable subset M of Z^n has a finite-fold Diophantine representation would falsify our conjecture for K=Z.

Full text: http://arxiv.org/abs/0901.2093  
References:
A. Kozlowski and A. Tyszka, A Conjecture of Apoloniusz Tyszka on the Addition of Rational Numbers, 2008,
Yu. Matiyasevich, Hilbert's tenth problem: what was done and what is to be done. Hilbert's tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), 1-47, Contemp. Math. 270, Amer. Math. Soc., Providence, RI, 2000
A. Tyszka, A system of equations, SIAM Problems and Solutions (electronic only), Problem 07-006, 2007,
A. Tyszka, Some conjectures on addition and multiplication of complex (real) numbers, Int. Math. Forum 4 (2009), no. 9-12, 521-530,
A. Tyszka, Bounds of some real (complex) solution of a finite system of polynomial equations with rational coefficients

The results of two papers will be presented:

T. Leighton, S. Rao "Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms"

Abstract: In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems. In particular, we show that for any n-node multicommodity flow problem with uniform demands, the max-flow for the problem is within an O(log n) factor of the upper bound implied by the min-cut. The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities.

O. Günlük "A New Min-Cut Max-Flow Ratio for Multicommodity Flows"

Abstract: We present an improved bound on the min-cut max-flow ratio for multicommodity flow problems with specified demands. To obtain the numerator of this ratio, capacity of a cut is scaled by the demand that has to cross the cut. In the denominator, the maximum concurrent flow value is used. Out new bound is proportional to log(k*) where k* is the cardinality of the minimal vertex cover of the demand graph.  

We consider the computational complexity of determining whether a system of equations over fixed algebra A has a solution. This leads to two problems, SysTermSat(A) and SysPolSat(A), in which equations are built out of terms or polynomials, respectively. We are interested in characterizing those algebras, for which SysPolSat can be solved in a polynomial time. The problem has been widely studied and is open in general. We prove that the Constraint Satisfaction Problem for relational structures is polynomially equivalent to SysTermSat over unary algebras. This gives that Dichotomy Conjecture for CSP is equivalent to Dichotomy Conjecture for SysTermSat over unary algebras. We also give other partial characterizations of computational complexity of SysTermSat(A), e.g. for algebras with generic operations taking only few values. This covers wide class of four-element unary algebras.  

INPUT: A relational structure $S$ of the same signature as R

OUTPUT: Is there a homomorphism ftom S into R

The central problem in this area is the Dichotomy Conjecture of Feder and Vardi stating that, for any relational structure R, CSP(R) is either solvable in polynomial time or NP-complete. I will talk about the universal algebraic approach to this problem and mention some recent developments.

Algorithmic meta-theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. We focuse on the model checking problem, which is to decide whether a given graph satisfies a given formula. Some restrictions of this problem to specific classes of graphs (with bounded treewidth, excluded minors etc.) turn out to be fixed-parameter tractable (fpt). We define combinatorial notions of tree decomposition, treewidth and local treewidth, and prove that MSO model checking on graphs with bounded treewidth and FO model checking on graphs with bounded local treewidth are fpt. The latter result uses Gaifman's Locality Theorem, which in one of basic tools in finite model theory. The talks are based on a paper by Martin Grohe [4].  
References:
[1] B. Courcelle. Graph rewriting: An algebraic and logic approach. Handbook of Theoretical Computer Science, volume B, pp. 194-242, 1990.
[2] J. Flum, M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing, 31(1):113-145, 2001.
[3] H. Gaifman. On local and non-local properties. Proceedings of the Herband Symposium, Logic Colloquium `81, pp. 105-135, 1982.
[4] M. Grohe. Logic, graphs, and algorithms. 2007.
http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf

Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn't be solved by classifying it as being either NP-complete or solvable in P. Nevertheless, efficient (polynomial-time or even NC) algorithms for restricted versions of GI have been found over the last four decades. Depending on the graph class, the design and analysis of algorithms for GI use tools from various fields, such as combinatorics, algebra and logic. In this talk, we collect several complexity results on graph isomorphism testing and related algorithmic problems for restricted graph classes from the literature. Further, we provide some new complexity bounds (as well as easier proofs of some known results) and highlight some open questions  
References:
J.Kobler, On Graph Isomorphism for Restricted Graph Classes

We consider a version of on-line graph coloring problem as a two person game with some additional conditions for players. Players are called Spoiler and Painter. Spoiler reveals a graph by putting or removing a node. But at each time the total number of nodes is bounded. Painter must assign a color to any new node such as two nodes connected by an edge have different colors. He cannot change colors of already colored nodes.
Chromatic number of such game for the class of graphs $C$, denoted by $\chi_C(p)$, is the smallest number of colors which is enough for Painter to color any graph presented by Spoiler, where $p$ is a bound for the size of graphs. We will show some lower and upper bounds of $\chi$-number for various classes of graphs.  

The game chromatic number of a graph G, denoted g(G), is the least number of colors guaranteeing a win for Ann. The main open problem is to find out how large is g(G) for planar graphs. Curiously, currently best strategy allows Ann to win (with 17 colors) even as a completely color blind person! I will present this and other techniques in a most recent treatise.

Joint work with Tomasz Bartnicki, Hal Kierstead and Xuding Zhu  

We show some types of combinatorial problems like edge colourings or graph decompositions expressing the full computational power of the NP class. Hence these problem classes contain also some problems of "exotic" complexity.

The first natural candidate that seems not to be equivalent to NP is the class called MMSNP (Monotone Monadic Strict NP) or Forbidden patterns problem. (A typical example for a language in the class: graphs with vertex set partitionable into two subsets without triangle.) This class is conjectured to contain only NP-complete and polynomial time solvable problems.

We prove that the class MMSNP can be expressed in the simpler terminology of relational structure homomorphism problems (called Constraint Satisfaction Problems): such a language contains for a fixed structure A the relational structures that can be mapped to A. homomorphically. The first such result was only a random equivalence. The proof of the deterministic equivalence uses some type of expander structures, a typical tool in derandomization.  

We construct a finite algebra generating a variety with PSPACE-complete membership problem first. Then we show another algebra with exponentially growing gamma function. In the final construction we use both of the previously mentioned algebras to produce a finite algebra that is able to model a computation of a Turing machine on an exponentially long tape. This gives an example of a finite algebra with EXPSAPCE-hard membership problem (on the other hand this problem is known to be in a 2-EXPTIME class).  

In the first problem [3] the goal is to schedule n jobs on m identical machines, without preemption, so that the jobs complete in the order of release times and the maximum flow time is minimized. This problem arises in network systems with aggregated links, when it is required that packets complete their arrivals at the destination in the order of their arrivals at the receiver. This requirement is imposed by the IEEE 802.3 standard describing link aggregation in Local Area Networks. We present a deterministic algorithm Block with competitive ratio O(\sqrt{n/m}) and show a matching lower bound even for randomized algorithms.

The second problem [1,2] is an online unit-job scheduling problem arising in networks supporting Quality of Service. Jobs are specified by release times, deadlines and nonnegative weights. The goal is to maximize the total weight of jobs, that are scheduled by their deadlines. We show that there does not exist a deterministic algorithm with competitive ratio better than 1.618 (the golden ratio). We also give a randomized algorithm with competitive ratio 1.582, showing that randomized algorithms are provably better than deterministic algorithms for this problem.  

It is known that the on-line coloring problem for arbitrary graphs is not competitive. However, restricting to special families of graphs, that have forbidden induced subgraphs (of some kind), the spoiler has his hands tied and the number of colors used by some on-line algorithms can be substantially reduced. We call these subgrahs: forcing structures. In my work I try to make a classification of competitive functions for various kind of families of graphs and also appoint the forcing structures for the on-line graph coloring. I was mostly looking for competitiveness for the graphs in the form of H-free: K_s-free, K_s,t-free, C_4-free, P_5-free and also for perfect and k-chordal graphs.  

A well-known method to represent a partially ordered set consists in associating to each element of P a subset of a fixed set S={1,..,k} such that the order relation coincides with subset inclusion. Given an order P, minimizing the size of the encoding, i.e. the cardinal of S, is however a difficult problem. The smallest size is called the 2-dimension of P. The paper details a proof that computing 2-dimension of a given poset is NPC. Reduction allows to prove the non-approximability of the problem. Later on the complexity of the 2-dimension for the class of trees is investigated. Authors present a 4-approximation algorithm for this class.  
References:
M. Habibb, L. Nourinea, O. Raynauda and E. Thierry, Computational aspects of the 2-dimension of partially ordered sets, Theoretical Computer Science 312 (2004), 401-431

One of the ways of expressing the complexity of a structure is the minimal "depth" of quantifiers in a formula that describes it. The presented paper discusses such complexity of two types of structures. The authors prove that the complexity of a random bit string is O(loglogn), with high probability, and the complexity of an ordered random graph - Theta(log*n), with high probability.  
References:
J.H. Spencer, K.St.John , The Complexity of Random Ordered Structure

Bartek presents that there is no online algorithm for chain covering problem of upgrowing posets using less than 2w-1 chains to cover a width w poset.  

In the well-studied on-line bin packing problem (BPP) we are given a set of items and a sequence of their sizes and are required to pack them into a minimum number of unit-capacity bins. The problem of finding the competitive ratio in the general case is open. In the analysed paper BPP is considered restricted to the case of two distinct item sizes. My talk based on this paper consists of an algorithm solving this particular case at an asymptotic competetive ratio of 4/3 and a proof that 4/3 is also here a valid lower bound.  
References:
G.Gutin, T.Jensen, A.Yeo, Optimal on-line bin packing with two item sizes, manuscript (2004)