21.11.2018 12:14
Marcin Briański
Computer science foundations
On the compressibility of finite languages and formal proofs by Sebastian Eberhard and Stefan Hetzl
We consider the minimal number of productions needed for a grammar to cover a finite language L as the grammatical complexity of L. We study this measure for several types of word and tree grammars and show that it is closely connected to well-known measures for the complexity of formal proofs in first-order predicate logic. We construct an incompressible sequence of finite word languages and transfer this and several other results about the complexity of word and tree languages to formal proofs
22.11.2018 14:00
Rafał Byczek, Bruno Pitrus
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów.

Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2-δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym.

W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)).

22.11.2018 16:00
Krzysztof Maziarz
Combinatorial Optimization
A refinement of choosability of graphs

Between the well-known concepts of k-colorability and k-choosability (also know as k-list colorability) lies a whole spectrum of more refined notions. This allows for seeing k-colorability and k-choosability under one unified framework. Exploring this, one immediately discovers interesting problems - for example, possible strengthenings of the four color theorem. We will take a look at these notions, prove some of their properties, and leave many conjectures and open problems.

27.11.2018 16:15
Dominika Salawa
Algorytmy Randomizowane i Aproksymacyjne
Induced trees in graphs of large chromatic number (Scott)
28.11.2018 12:14
Jacek Kurek i Bruno Pitrus
Computer science foundations
The subject of enumerative combinatorics is both classical and modern. It is classical, as the basic counting questions go back millennia; yet it is modern in the use of a large variety of the latest ideas and technical tools from across many areas of mathematics. The remarkable successes from the last few decades have been widely publicized; yet they come at a price, as one wonders if there is anything left to explore. In fact, are there enumerative problems that cannot be resolved with existing technology? In this paper we present many challenges in the field from the computational complexity point of view, and describe how recent results fit into the story. 
28.11.2018 16:15
Piotr Kawałek
Theoretical computer science
29.11.2018 16:00
Jan Derbisz
Combinatorial Optimization
Choosability of Planar Graphs
05.12.2018 12:14
Bartłomiej Puget
Computer science foundations
Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe lambda calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed lambda calculus. In contrast to the original definition of safety, our calculus does not constrain types (to be homogeneous). We show that in the safe lambda calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen. We also propose an adequate notion of beta-reduction that preserves safety. In the same vein as Schwichtenberg’s 1976 characterization of the simply-typed lambda calculus, we show that the numeric functions representable in the safe lambda calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a characterization of representable word functions. We then study the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by P-incrementally justified strategies. Consequently pointers in the game semantics of safe lambda terms are only necessary from order 4 onwards. 
06.12.2018 16:00
Jakub Nowak
Combinatorial Optimization
Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

Team Rocket. Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies. 2018.

12.12.2018 12:14
Dominik Gryboś
Computer science foundations
Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus by Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca
In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k \geq 0, is given, by a type assignment system for a stratified lambda - calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types. 
19.12.2018 12:14
Jakub Łabaj i Gabriela Czarska
Computer science foundations
Programming Languages Capturing Complexity Classes by LARS KRISTIANSEN and PAUL J. VODA
We investigate an imperative and a functional programming language. The computational power of fragments of these languages induce two hierarchies of complexity classes. Our first main theorem says that these hierarchies match, level by level, a complexity-theoretic alternating space-time hierarchy known from the literature. Our second main theorems says that a slightly different complexity-theoretic hierarchy (the Goerdt-Seidl hierarchy) also can be captured by hierarchies induced by fragments of the programming languages. Well known complexity classes like LOGSPACE, LINSPACE, P, PSPACE  etc., occur in the hierarchies.
19.12.2018 16:15
Grzegorz Gutowski
Theoretical computer science
09.01.2019 12:14
Krzysztof Turowski
Purdue University, USA
Computer science foundations
16.01.2019 12:14
Rafał Byczek i Paweł Mader
Computer science foundations
A theory of linear typings as flows on 3-valent graphs by Noam Zeilberger
Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or “maps”), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classical notion of an abelian group-valued “flow” on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3-valent graph with boundary) valued in a more general algebraic structure consisting of a preordered set equipped with an “implication” operation and unit satisfying composition, identity, and unit laws. Interesting questions and results from the theory of flows (such as the existence of nowhere-zero flows) may then be re-examined from the standpoint of lambda calculus and logic. For example, we give a characterization of when the local flow relations (across vertices) may be categorically lifted to a global flow relation (across the boundary), proving that this holds just in case the underlying map has the orientation of a lambda term. We also develop a basic theory of rewriting of flows that suggests topological meanings for classical completeness results in combinatory logic, and introduce a polarized notion of flow, which draws connections to the theory of proof-nets in linear logic and to bidirectional typing. 
23.01.2019 12:14

Computer science foundations

Constructor rewriting systems are said to be cons-free if, roughly, constructor terms in the right-hand sides of rules are subterms of the left-hand sides; the computational intuition is that rules cannot build new data structures. In programming language research, cons-free languages have been used to characterize hierarchies of computational complexity classes; in term rewriting, cons-free first-order TRSs have been used to characterize P. We investigate cons-free higher-order term rewriting systems, the complexity classes they characterize, and how these depend on the type order of the systems. We prove that, for every K ≥ 1, left-linear cons-free systems with type order K characterize $E^K KTIME$ if unrestricted evaluation is used (i.e., the system does not have a fixed reduction strategy).

The main difference with prior work in implicit complexity is that (i) our results hold for non-orthogonal TRSs with no assumptions on reduction strategy, (ii) we consequently obtain much larger classes for each type order ($E^K KTIME$ versus $EXP^{K−1}TIME$),  and (iii) results for cons-free term rewriting systems have previously only been obtained 
for K = 1, and with additional syntactic restrictions besides cons-freeness and left-linearity. Our results are among the first implicit characterizations of the hierarchy $E = E^1 TIME \subset 2TIME ( · · ·$ . 

Our work confirms prior results that having full non-determinism (via overlapping rules) does not directly allow for characterization of non-deterministic complexity classes like NE. We also show that non-determinism makes the classes characterized highly sensitive to minor syntactic changes like admitting product types or non-left-linear rules.

Poprzednie referaty

20.11.2018 16:15
Dawid Tracz
Algorytmy Randomizowane i Aproksymacyjne
Finding Cliques in Social Networks: A New Distribution-Free Model (Fox, Roughgarden, Seshadhri, Wei, Wein)
15.11.2018 14:00
Tomasz Zieliński, Michał Zwonek
On the Complexity of the (Approximate) Nearest Colored Node Problem
Given a graph G = (V, E) where every vertex has assigned a color, we ask for the approximate distance between the selected vertex v and the closest color c. We present an oracle of a stretch 4k-5 using O(kn sigma^(1/k)) space and O(log k) query time. Next, we prove that having only an estimate of order O(polylog(n)) we can answer the query dist(v, c) in O(1) time. Finally, we show the connection between lambda-OuMv and dist(v, c) problems.
14.11.2018 16:15
21.11.2018 16:15
Michał Seweryn
Theoretical computer science
Bumping a ladder

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

14.11.2018 12:14
Mateusz Tokarz
Computer science foundations
Enumerating Proofs of Positive Formulae by GILLES DOWEK AND YING JIANG
We provide a semi-grammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proof-term of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F.
13.11.2018 16:15
Mateusz Pabian
Algorytmy Randomizowane i Aproksymacyjne
New approximation algorithm for (1,2)-TSP (Adamaszek, Mnich, Paluch)
08.11.2018 16:15
Marcin Muszalski
Combinatorial Optimization
On the queue-number of graphs with bounded tree-width

In this talk I will present upper bound for a queue-number of graphs with bounded tree-width obtained by Veit Wiechert. The new upper bound, 2k - 1, improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. Additionally I will show his construction of k-trees that have queue-number at least k + 1. The construction solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queue-number of 2-trees is equal to 3.

Veit Wiechert. On the queue-number of graphs with bounded tree-width. Electronic Journal of Combinatorics, 24(1):1-14, 2017.

Marcin Muszalski. Queue-number of graphs with bounded tree-width - Veit Wiechert. slides. 2018.

08.11.2018 14:00
Weronika Grzybowska, Paweł Mader
Hamming distance completeness and sparse matrix multiplication
Authors of the paper show that a broad class of (+, <>) vector products (for binary integer functions <>) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Those results imply equivalence (up to polylog factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. Additionally, they show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n×(n · d) and (n · d)×n, each with (n · d) non-zero entries.
07.11.2018 12:14
Paweł Palenica
Computer science foundations
On Randomised Strategies in the λ-Calculus by Ugo Dal Lago and Gabriele Vanoni
In this work we introduce randomized reduction strategies - a notion already studied in the context of abstract reduction systems - for the lambda-calculus. We develop a simple framework that allows us to prove if a probabilistic strategy is positive almost-surely normalizing. Then we propose a simple example of probabilistic strategy for the lambda-calculus that has such a property and we show why it is non-trivial with respect to classical deterministic strategies such as leftmost-outermost or rightmostinnermost. We conclude studying this strategy for two classical sub- lambda calculi, namely those duplication and erasure are syntactically forbidden.
06.11.2018 16:15
Szymon Łukasz
Algorytmy Randomizowane i Aproksymacyjne
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (A. Bhangale)

We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,

1) It is NP-hard to color it with log^delta n colors for some delta>0.

2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.

31.10.2018 12:14
Rafał Burczyński
Computer science foundations
A Hitchhiker’s Guide to descriptional complexity through analytic combinatorics by Sabine Broda, António Machiavelo, Nelma Moreira and Rogério Reis
Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several $\epsilon-NFA$ constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the $\epsilon-NFA$ constructions approaches the corresponding $\epsilon-free NFA$ construction, asymptotically and on average.
30.10.2018 16:15
Wiktor Daniec
Algorytmy Randomizowane i Aproksymacyjne
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
25.10.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
A new variant of the game of cops and robber

We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,...,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,2,...,dk) whose components di=dG(u,vi), i=1,2,...,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localise him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously. The aim of the talk is to present results concerning 2-trees, outerplanar graphs and planar graphs. This is a joint work with Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, and Małgorzata Śleszyńska-Nowak.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Centroidal localization game. arXiv, pages 1-15, 2017.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Localization game on geometric and planar graphs. arXiv, pages 1-15, 2017.

25.10.2018 14:00
Filip Bartodziej, Vladyslav Hlembotskyi
Fine-grained Lower Bounds on Cops and Robbers
Thorough policemen or an elusive thief? At this seminar we’ll find out who comes out on top, how fast/slow can we find it out and how many cops will suffice to capture even the legendary Frank Abagnale. Our deliberations will be based around the popular cops and robbers game played on graphs. The presented results require SETH/ETH assumption.
24.10.2018 12:14
Szymon Stankiewicz
Computer science foundations
Encoding Turing Machines into the Deterministic Lambda Calculus by Ugo Dal Lago and Beniamino Accattoli

This note is about encoding Turing machines into the lambda -calculus. The encoding we show is interesting for two reasons:

1. Weakly strategy independent : the image of the encoding is a very small fragment of the lambda - calculus, that we call the deterministic lambda -calculus det. Essentially, it is the CPS (continuation-passing style) lambda -calculus restricted to weak evaluation (i.e., not under abstractions). In det every term has at most one redex, and so all weak strategies collapse into a single deterministic evaluation strategy, because there are no choices between redexes to be made. The important consequence of this property is that every weak evaluation strategy then allows to simulate Turing machines,as well as any strong strategy reducing weak head redexes (or even only weak head redexes) first.

2. Linear overhead: the simulation is very efficient, when taking the number of beta-steps as the time cost model for the deterministic lambda -calculus. The simulation in det indeed requires a number of beta-steps that is linear in the number of transitions of the encoded Turing machine, which is the best possible overhead. Therefore, not only all weak strategies simulate Turing
machines, but they all do it efficiently.

18.10.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
Local Dimension is Unbounded for Planar Posets

In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter.

Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017.

18.10.2018 14:00
Jan Mełech, Rafał Burczyński
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
The Subset-Sum problem asks to find such a subset T of given multiset S of natural numbers (|S| = n) that sum of it's elements is equal to given t.
The authors present a simple probabilistic solution to this well-known NP-complete problem based on techniques such as Fast Fourier Transform and generating
functions. The running time of the algorithm is O((n+t)*polylog(t)) and the error probability is O(1/(n+t)). Even though this time complexity was
achieved before, the presented work is simpler as its description is only a few pages long.
17.10.2018 16:15
24.10.2018 16:15
Patryk Mikos
Theoretical computer science
Does the representation matter?

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,
  • K1,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.

17.10.2018 12:14
Vladyslav Hlembotskyi
Computer science foundations
Limited Automata and Regular Languages by Giovanni Pighizzini and Andrea Pisoni

Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d \geq 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schutzenberger representation for context-free languages,
we present a new conversion from context-free languages into 2-limited automata.


11.10.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
A Tight Bound for Shortest Augmenting Paths on Trees

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=(WB, 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. This is a joint work with Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz. A Tight Bound for Shortest Augmenting Paths on Trees. arXiv, pages 1-22, 2017.

11.10.2018 14:00
Dawid Pyczek, Michał Zieliński
On the Worst-Case Complexity of TimSort
TimSort is a very interesting sorting algorithm, which was introduced to Python in 2002. This popular algorithm is being successfully used all around the world, for its incredibly fast execution on partially sorted data.
There has been, however, no formal proof of the algorithm's pessimistic complexity. This paper proves that TimSort runs in O(n log n).
There will also be a proof that Python’s TimSort running time is in O(n+n log ρ), where ρ is the number of runs. Obviously, the first complexity can be deduced from the second one, but both of them helps to better understand how TimSort works.
As a byproduct of the analysis a new bug was found in Java implementations of TimSort.
10.10.2018 16:15
Andrzej Dorobisz
Theoretical computer science
Induced subgraphs of graphs with large chromatic number

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.

10.10.2018 12:14
Michał Zieliński
Computer science foundations
Lambda Theories allowing Terms with a Finite Number of Fixed Points by BENEDETTO INTRIGILA and RICHARD STATMAN
A natural question in the lambda calculus asks what is the possible number of fixed points of a combinator (closed term). A complete answer to this question is still missing (Problem 25 of TLCA Open Problems List) and we investigate the related question about the number of fixed points of a combinator in lambda-theories. We show the existence of a recursively enumerable lambda theory where the number is always one or infinite. We also show that there are lambda-theories such that some terms have only two fixed points. In a first example, this is obtained by means of a non-constructive (more precisely non-r.e.) lambda-theory where the range property is violated. A second, more complex example of a non-r.e. Lambda-theory (with a higher unsolvability degree) shows that some terms can have only two fixed points while the range property holds for every term.
04.10.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
Some open problems
03.10.2018 12:14
Jarosław Duda
Instytut Informatyki UJ
Computer science foundations
Krótkie wprowadzenie do ANS, MERW i pól Markova
Na seminarium spróbuję zainteresować kilkoma z tematów, którymi się zajmowałem, np. kodowaniem Asymmetric Numeral Systems, które jest obecnie używane w produktach Apple, Facebook, Google. Opowiem też o Maximal Entropy Random Walk, czyli jak optymalnie wybierać błądzenie przypadkowe na grafie - z perspektywy zastosowań do maksymalizacji ilości przechowywanej informacji, zrozumienia i naprawienia rozbieżności między dyfuzją a mechaniką kwantową, analizy obrazów, sieci społecznych, czy rekonstrukcji traktów nerwowych. Tematem łączącym powyższe będą pola Markova, czyli wielowymiarowe uogólnienie procesów Markova, o których też krótko opowiem z przykładem zastosowania do poprawienia pojemności dysków twardych. Slajdy do seminarium można znaleźć na:
14.06.2018 16:15
Mateusz Twaróg, Patryk Urbański, Łukasz Majcher
Combinatorial Optimization
Progress in the Arachne Project
13.06.2018 12:14
Marcin Briański
Computer science foundations

A coarse description of a set A \subset \omega  is a set D \subset \omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1- genericity in place of weak 2-randomness. In the other direction, we show that if A \leq_T \emptyset is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set.


07.06.2018 17:15
Krzysztof Maziarz
Combinatorial Optimization
The chromatic number of the plane is at least 5​

The Hadwiger-Nelson problem asks for the minimum number of colors required to color the plane, in such a way, that any two points at distance exactly one are assigned different colors. Albeit its simple definition, no significant progress on the question was made for nearly a century. In the discussed paper, Aubrey D. N. J. de Grey has shown a set of points in the plane, such that 5 colors are necessary to color it properly, thus improving a long-standing lower bound of 4 colors. Interestingly, the smallest such set discovered so far has 1581 vertices.

The chromatic number of the plane is at least 5, Aubrey D.N.J. de Grey
07.06.2018 16:15
Szymon Łukasz
Combinatorial Optimization
Dynamic F-free Coloring of Graphs

An F-free coloring is a coloring of a graph such that each color induces an F-free graph. In this talk we consider dynamic F-free coloring which can be interpreted as a game of Presenter and Painter. In each move Presenter presents new vertices along with the edges between them and already known vertices. In the same move Presenter can also discolor arbitrary vertices and request Painter to color some vertices. The problem we consider can be stated as follows: For a given graph G, is there a sequence of moves for which the greedy algorithm uses at least k colors during dynamic F-free coloring of G. We will show that for some classes of graphs this problem is decidable in polynomial time (for fixed F and k) in the case where F is 2-connected or F is path of length 2.

Piotr Borowiecki, Elżbieta Sidorowicz, Dynamic F-free Coloring of Graphs, Graphs and Combinatorics 2018, Volume 34, Issue 3, pp 457-475
06.06.2018 12:14
Bruno Pitrus
Computer science foundations
Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger

The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.



30.05.2018 16:15
06.06.2018 16:15
Grzegorz Herman
Theoretical computer science
Relational parsing: a clean generalized parsing algorithm.

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.

30.05.2018 12:14
Bartłomiej Puget
Computer science foundations

In the Simply Typed lambda calculus Statman investigates the reducibility relation between types: for types freely generated using \arrow and a single ground type 0, define A \leq B if there exists a lambda definable injection from the closed terms of type A into those of type B. Unexpectedly, the induced partial order is the (linear) well-ordering (of order type) \omega + 4.


24.05.2018 16:15
Marcin Briański
Combinatorial Optimization
How many ants does it take to find the food?

In this talk we will consider the ANTS (Ants Nearby Treasure Search) problem: consider n agents (ants), controlled by finite automata (or PDAs) exploring an infinite grid attempting to locate a hidden treasure. The question we want to answer is: how many agents are necessary to accomplish this task in (expected) finite time? Of course, the answer will depend on the way we model this situation. We will consider synchronous as well as asynchronous environment, agents with access to randomness as well as deterministic ones, agents controlled by PDA as well as finite automata and various combinations thereof. In most cases established bounds are tight, however in certain cases there is still ample room for improvement (which some might consider interesting).

Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, Roger Wattenhofer, How many ants does it take to find the food?, Theoretical Computer Science Volume 608, Part 3, 10 December 2015, Pages 255-267
23.05.2018 12:14

Computer science foundations
17.05.2018 16:15
Marcin Muszalski
Combinatorial Optimization
On the Number of Maximum Empty Boxes Amidst n Points

I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant):
Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S.
They created first superlinear lower bound for the number of maximum-volume empty boxes amidst n points in R d (d ≥ 3). I would like to present it and show a prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log(n) 2^α(n) ), where α(n) is the extremely slowly growing inverse of Ackermann’s function. The previous best bound for this problem, O(n^2 ), is due to Naamad, Lee, and Hsu (1984).

Adrian Dumitrescu, Minghui Jiang, On the Number of Maximum Empty Boxes Amidst n Points, Discrete & Computational Geometry, Volume 59 (3), 742-756, 2018
16.05.2018 12:14
Maciej Czerwiński
Computer science foundations
On Type Inference in the Intersection Type Discipline by Gerard Boudol and Pascal Zimmer
We introduce a new unification procedure for the type inference problem in the intersection type discipline. We show that unification exactly corresponds to reduction in an extended  lambda calculus, where one never erases arguments that would be discarded by ordinary β-reduction. We show that our notion of unification allows us to compute a principal typing for any strongly normalizing lambda expression.
10.05.2018 16:15
Jakub Szarawski
Combinatorial Optimization
Faster approximation schemes for the two-dimensional knapsack problem

In 2008 Klaus Jansen and Roberto Solis-Oba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented.

S. Heydrich, A. Wiese, Faster approximation schemes for the two-dimensional knapsack problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 79-98

09.05.2018 12:14
Dominika Salawa
Computer science foundations
The Hiring Problem and Permutations by Margaret Archibald and Conrado Martínez

The hiring problem has been recently introduced by Broder et al. in last year’s ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem.

26.04.2018 16:15
Sylwester Klocek
Combinatorial Optimization
Colouring of (P3∪P2)-free graphs

In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs.

Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)-free graphs, Graphs and Combinatorics, Volume 34 (1), 2018
25.04.2018 16:15
Jacek Krzaczkowski
Theoretical computer science
Complexity of solving equations

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..

25.04.2018 12:00
Rafał Burczyński
Computer science foundations
How to select a loser
Consider the following game: everyone from a group of n people flips a coin with result either 0 or 1, both equally probable; if no one gets a 0, the round is repeated, otherwise people with 1's are considered "winners" and the game continues only with participants who got 0's. The process continues until there is one person left, who is called "loser". We can picture this process as a binary tree and analyze some of its properties in average case. The analysis is not completely trivial, in particular one may find application for tools such as Mellin transform.
19.04.2018 16:15
Grzegorz Jurdziński
Combinatorial Optimization
Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density

Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles.

Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109

18.04.2018 12:00
Rafał Burczyński
Computer science foundations
Mellin transforms and asymptotics
We will introduce Mellin transform, which may be used for the asymptotic analysis of a particular class of sums. I will start with basic properties and then present fundamental correspondence between the asymptotic expansion of a function at 0 or infinity and singularities of its transform. Finally we will show some combinatorial applications of the transform.
12.04.2018 16:15
Maciej Woźniak
Combinatorial Optimization
Find Your Place: Simple Distributed Algorithms for Community Detection

Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if:

  • G is connected and not bipartite,
  • |V_1| = |V_2|
  • V_1 \cap V_2 = \emptyset
  • Every vertex has degree d
  • Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1,
  • Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2.

We define (weak) block reconstruction of graph as two-coloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact.
I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for non-regular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia

11.04.2018 12:14
Weronika Grzybowska
Computer science foundations
Average complexity of Moore’s and Hopcroft’s algorithms by Julien David
In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore’s state minimization algorithm is O(n log (log n)),  where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hopcroft’s algorithm is characterized, for which the algorithm will be proved to be always faster than Moore’s algorithm. Finally, we present experimental results on the usual implementations of Hopcroft’s algorithm.
05.04.2018 16:15
Anna Kobak
Combinatorial Optimization
On tree-partition-width

A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2.

David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253

04.04.2018 16:15
Bartosz Walczak
Theoretical computer science
Sparse Kneser graphs are Hamiltonian

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).

04.04.2018 12:14
Vladyslav Hlembotskyi
Computer science foundations
A graph theoretic approach to automata minimality by Antonio Restivo and Roberto Vaglica
The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
28.03.2018 16:15
Grzegorz Guśpiel
Theoretical computer science
On the Complexity of Crossing Minimization
For a bipartite graph G with vertex bipartition (X, Y), a two-layer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines LX and LY, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a two-layer drawing is a two-layered graph. We study basic graph problems on two-layered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)-path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.
This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi.
28.03.2018 12:00
Szymon Stankiewicz
Computer science foundations
Introduction to Higher-Order Categorical Logic - continuation
22.03.2018 16:15
Aleksandra Mędrek
Combinatorial Optimization
The Matching Problem in General Graphs is in Quasi-NC

Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached.

Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017

21.03.2018 12:00
Szymon Stankiewicz
Computer science foundations
Introduction to Higher-Order Categorical Logic by Lambec and Scott
15.03.2018 16:15
Dawid Pyczek
Combinatorial Optimization
Punctured combinatorial Nullstellensätze

This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problem-solving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions.

Simeon Ball, Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica, September 2009, Volume 29, Issue 5, pp 511–522

14.03.2018 16:15
Michael Kompatscher
Charles University in Prague
Theoretical computer science
CSPs of infinite structures and equations in oligomorphic algebras
In 1998 Feder and Vardi famously conjectures that the constraint satisfaction problem (CSP) of a finite structure is either in P or NP-complete. Universal algebra turned out to be the main tool in tackling their conjecture and lead to two recent proofs, showing that CSP(A) is in P if the polymorphism algebra associated with A is a Taylor algebra, and NP-complete otherwise.
For CSPs of structures with infinite domains this universal algebraic approach fails badly in general. However, if the automorphism group of the structure is "sufficiently big", i.e. oligomorphic, many results can be transferred from the finite case. We survey results about the equational structure of oligomorphic algebras and their applications to constraint satisfaction problems.
14.03.2018 12:14
Dawid Pyczek i Jakub Rówiński
Computer science foundations
Asymptotic Density and the Theory of Computability by CARL JOCKUSCH AND PAUL SCHUPP
The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few
easy proofs to illustrate the flavor of the subject. In complexity theory, classes such as P and NP are defined by using worst-case measures. That is, a problem belongs to the class if there is an algorithm solving it which has a suitable bound on its running time over all instances of the problem. Similarly, in computability theory, a problem is classified as computable if there is a single algorithm which solves all instances of the given problem. There is now a general awareness that worst-case measures may not give a good picture of a particular algorithm or problem since hard instances may be very sparse. The paradigm case is Dantzig’s Simplex Algorithm for linear programming problems. This algorithm runs many hundreds of times every day for scheduling and transportation problems, almost always very quickly. There are clever examples of Klee and Minty showing that there exist instances for which the Simplex Algorithm must take exponential time, but such examples are not encountered in practice. Observations of this type led to the development of average-case complexity by Gurevich and by Levin independently. There are different approaches to the average-case complexity, but they all involve computing the expected value of the running time of an algorithm with respect to some measure on the set of inputs. Thus the problem must be decidable and one still needs to know the worst-case complexity. Another example of hard instances being sparse is the behavior of algorithms for decision problems in group theory used in computer algebra packages. There is often some kind of an easy “fast check” algorithm which quickly produces a solution for “most” inputs of the problem. This is true even if the worst-case complexity of the particular problem is very high or the problem is even unsolvable. Thus many group-theoretic decision problems have a very large set of inputs where the (usually negative) answer can be obtained easily and quickly.
20.06.2018 12:15
Wojciech Szpankowski
Purdue University USA
Computer science foundations
Analytic Information Theory: From Shannon to Knuth and Back
08.03.2018 16:15
Jakub Rówiński
Combinatorial Optimization
On the 1/3–2/3 Conjecture

Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an α-balanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2-balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams.

Emily J. Olson, Bruce E. Sagan, On the 1/3--2/3 Conjecture, Order, 2018

07.03.2018 12:14
Jarosław Duda
Instytut Informatyki UJ
Computer science foundations
Some nonstandard approaches to hard computational problems

I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm.  I will start with briefly explaining mechanism used in Shor algorithm, compressed sensing, and the problem with global optimization formulations used in adiabatic
quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem.  Finally discuss the difficulty of the graph isomorphism problem
on the most problematic cases: strongly regular graphs, geometric perspective on this problem, and some new approach to rotation invariants for this purpose.



01.03.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
Some open problems
28.02.2018 16:15
Piotr Micek
Theoretical computer science
Seymour's conjecture on 2-connected graphs of large pathwidth

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.

25.01.2018 16:15
Bartłomiej Bosek
Combinatorial Optimization
News about Combinatorial Nullstellensatz

I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems.

Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. arXiv:1310.6482 (2014), pp 1-44.

18.01.2018 16:15
Jarek Duda
Combinatorial Optimization
Some nonstandard approaches to hard computational problems

I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem.

Jarek Duda. Some unusualapproaches to hard computational problems. slides.

17.01.2018 16:15
24.01.2018 16:15
Andrzej Dorobisz
Theoretical computer science
Online bipartite matching with amortized O(log²n) replacements

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

by Aaron Bernstein, Jacob Holm and Eva Rotenberg
17.01.2018 12:00
Bartłomiej Puget i Dominika Salawa
Computer science foundations
Chapters 8.5 - 8.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet
11.01.2018 16:15
Maciej Woźniak, Dawid Pyczek
Combinatorial Optimization
Online Vertex Cover and Matching: Beating the Greedy Algorithm

Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal water-filling algorithm with competitive ratio 1/(1-1/e) . The main contribution of this paper is a 1.901-competitive algorithm for vertex cover in general graphs which beats the well-known trivial 2-competitive algorithm. The next major result is a primal-dual analysis of given algorithm that implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.

Yajun Wang, Sam Chiu-wai Wong. Online Vertex Cover and Matching: Beating the Greedy Algorithm. arXiv (2013), pp 1-21.