Poprzednie referaty

22.01.2020 16:15
Krzysztof Turowski
Theoretical computer science
Degree Distribution of Dynamic Graphs Generated by a Duplication-Divergence Models
We analyze the structure of dynamic graphs generated from duplication models in which a new vertex selects an existing vertex and copies some of its neighbors and then we add some random divergence. We analyze various graph parameters like mean degree, number of open triangles, number of triangles, number of vertices of degree k or maximum degree in a graph generated from such models. We provide asymptotic analysis of expected values and tail behavior of these parameters. We also point to further extensions of this approach towards computing symmetries in these graphs and algorithms for graph compression.
 
Joint work with Philippe Jacquet, Alan Frieze and Wojciech Szpankowski
22.01.2020 12:15
Weronika Grzybowska i Mateusz Tokarz
Computer science foundations
On two subclasses of Motzkin paths and their relation to ternary trees by Helmut Prodinger, Sarah J. Selkirk and Stephan Wagner
Two subclasses of Motzkin paths, S-Motzkin and T-Motzkin paths, are introduced. We provide bijections between S-Motzkin paths and ternary trees, S-Motzkin paths and non-crossing trees, and T-Motzkin paths and ordered pairs of ternary trees. Symbolic equations for both paths, and thus generating functions for the paths, are provided. Using these, various parameters involving the two paths are analyzed.
16.01.2020 17:00
Gabriela Czarska
Combinatorial Optimization
Driver surge pricing

Authors study Uber's pricing mechanisms from the perspective of drivers, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. They present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings.

Nikhil Garg, Hamid Nazerzadeh. Driver Surge Pricing. arXiv. 2019.

16.01.2020 16:15
Bartosz Podkanowicz
Combinatorial Optimization
Planar graphs have bounded queue-number

The paper presents proof that the queue number of planar graphs is bounded. It also mentions generalizations of the result and other theorems that have similar proofs.

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood. Planar graphs have bounded queue-number. arXiv. 2019.

16.01.2020 14:15
Katarzyna Król, Paweł Mader
Algorytmika
On the Complexity of Lattice Puzzles [Kobayashi et al.]
In this paper, authors investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n×n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes.
15.01.2020 16:15
Michał Seweryn
Theoretical computer science
Erdös-Hajnal properties for powers of sparse graphs

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|=Ω(n1-ε) 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.

 

 

Joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk
15.01.2020 12:15
Wojciech Grabis
Computer science foundations
Ant colony optimization theory: A survey by Marco Dorigoa and Christian Blumb
Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method’s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we reviewsome convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future.
09.01.2020 17:00
Wojtek Grabis
Combinatorial Optimization
Algorithms for Destructive Shift Bribery.

Destructive Shift Bribery is a problem in which we are given an election with a set of candidates and a set of voters, a budget , a despised candidate and price for shifting the despised candidate in the voters rankings. Our objective is to ensure that selected candidate cannot win the election. We're going to study the complexity of this problem under diffrent election methods.

Andrzej Kaczmarczyk, Piotr Faliszewski. Algorithms for Destructive Shift Bribery. arXiv. 2018.

09.01.2020 16:15
Dominik Gryboś
Combinatorial Optimization
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice

The paper shows that the Diffie-Hellman protocol is not as secure as we thought. The authors present the Logjam attack, which consists in quickly calculating discrete logarithms based on previously performed calculations. This can be done because many websites use the same prime numbers in the message encryption process.

David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelink, Paul Zimmermann. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. WeakDH.org.

08.01.2020 12:15
Piotr Gaiński
Computer science foundations
How Similar Are Two Elections by Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Stanisław Szufa and Nimrod Talmon
We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as d-ISOMORPHISM DISTANCE (d-ID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the d-ISOMORPHISM DISTANCE problems generalize various classic rank-aggregation methods (e.g., those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice.
19.12.2019 17:00
Kamil Kropiewnicki
Combinatorial Optimization
Impossibility of Distributed Consensus with One Faulty Proces

 

he consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.

Authors of the paper were awarded a Dijkstra Prize for this work - given to the most influential papers in distributed computing.

Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the Association for Computing Machinery, 32(2), 1985, 374-382.

19.12.2019 16:15
Filip Bartodziej
Combinatorial Optimization
How to eat 4/9 of a pizza

Unevenly cut pizza is a frustrating occurrence. How can we then make sure that a friend is not trying to reduce our portion of the delicious meal? We will present a strategy which guarantees that one will leave the table satisfied, assuming that they started eating first.

Kolja Knauer, Piotr Micek, Torsten Ueckerdt. How to eat 4/9 of a pizza. arXiv. 2008.

18.12.2019 12:15
Bartosz Podkanowicz
Computer science foundations
Riordan arrays and combinatorial sums by Renzo Sprugnoli
The concept of a Riordan array is used in a constructive way to find the generating function of many combinatorial sums. The generating function can then help us to obtain the closed form of the sum or its asymptotic value. Some examples of sums involving binomial coefficients and Stirling numbers are examined, together with an application of Riordan arrays to some walk problems.
12.12.2019 17:00
Krzysztof Michalik
Combinatorial Optimization
Coloring planar graphs with 3 colors and no large monochromatic components

I will present a proof that there exists a function f(d), such that there exists a 3-coloring of any planar graph G in which each monochromatic subgraph has at most f(d) vertices, where d is the degree of the highest-degree vertex in G.

Louis Esperet, Gwenaël Joret. Coloring planar graphs with three colors and no large monochromatic components. arXiv, 1303.2487. 2013.

12.12.2019 16:15
Mateusz Kaczmarek
Combinatorial Optimization
Hadwiger’s conjecture

Survey of Hadwiger's Conjecture from 1943, that for all t ≥ 0, every graph is either t-colorable or has a subgraph that can be contracted to the complete t+1 vertices graph. This conjecture is the tremendous strengthening of the four-color problem also known as map coloring problem.

Paul Seymour. Hadwiger’s conjecture.

12.12.2019 14:15
Krzysztof Pióro, Krzysztof Potępa
Algorytmika
Linear-Space Data Structures for Range Mode Query in Arrays [Chan, Durocher, Larsen, Morrison, Wilkinson]
A mode of a multiset S is an element a ∈ S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n)*log log n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n/log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) x sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n1−1/2d) time) and for halfspace range mode in higher dimensions (queries in O(n1−1/d^2) time).
11.12.2019 16:15
Adam Polak
Theoretical computer science
Monochromatic triangles, intermediate matrix products, and convolutions

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(n3/2) time and 3SUM is in O(n2) 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.

11.12.2019 12:15
Mateusz Górski
Computer science foundations
A Modal Characterization Theorem for a Probabilistic Fuzzy Description Logic by Paul Wild, Lutz Schroder, Dirk Pattinson and Barbara Konig.
The fuzzy modality probably is interpreted over probabilistic type spaces by taking expected truth values. The arising probabilistic fuzzy description logic is invariant under probabilistic bisimilarity; more informatively, it is non-expansive wrt. a suitable notion of behavioural distance. In the present paper, we provide a characterization of the expressive power of this logic based on this observation: We prove a probabilistic analogue of the classical van Benthem theorem, which states that modal logic is precisely the bisimulation-invariant fragment of first-order logic. Specifically, we show that every formula in probabilistic fuzzy first-order logic that is non-expansive wrt. behavioural distance can be approximated by concepts of bounded rank in probabilistic fuzzy description logic.
05.12.2019 16:15
Kornel Dulęba
Combinatorial Optimization
The Return of Coppersmith’s Atack: Practical Factorization of Widely Used RSA Moduli

During the seminar I will discuss a clever attack on RSA library used in Infineon chips. Researchers discovered that the prime factors used for constructing private keys have a peculiar form. This allowed them to use a modified version of Coppersmith algorithm to recover private key basing on their public counterpart in a reasonable time for keys up to 2048 bit long.

Dusan Klinec, Vashek Matyas, Matus Nemec, Marek Sys, Petr Svenda. The Return of Coppersmith’s A‚ack: Practical Factorization of Widely Used RSA Moduli.

04.12.2019 12:15
Michał Zwonek
Computer science foundations
Probably Half True: Probabilistic Satisfability over Lukasiewicz Infnitely-valued Logic by Marcelo Finger and Sandro Preto
We study probabilistic-logic reasoning in a context that allows for "partial truths", focusing on computational and algorithmic properties of non-classical Lukasiewicz In nitely-valued Probabilistic Logic. In particular, we study the satis ability of joint probabilistic assignments, which we call LIPSAT. Although the search space is initially in nite, we provide linear algebraic methods that guarantee polynomial  size witnesses, placing LIPSAT complexity in the NP-complete class. An exact satis ability decision algorithm is presented which employs, as a subroutine, the decision problem for Lukasiewicz In nitely-valued (non probabilistic) logic, that is also an NP-complete problem. We develop implementations of the algorithms described and discuss the empirical presence of a phase transition behavior for those implementations.
28.11.2019 16:15
Mikołaj Twaróg
Combinatorial Optimization
A Short Guide to Hackenbush

Hackenbush is a two player game played on a graph with a few marked vertices. Players alternate turns. Each turn consists of removing one edge from the graph and all vertices that lost their connection to all marked ones. Player, that can't make a move, loses. I will present three different variants of Hackenbush(Red-Blue Hackenbush, Green Hackenbush and R-G-B Hackenbush) with methods to determine, which player has a winning strategy.

Padraic Bartlett. A Short Guide to Hackenbush. VIGRE REU 2006.

28.11.2019 14:15
Katarzyna Bułat, Dawid Tracz
Algorytmika
Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time [P. Parys]

Gry parzystości to gry pomiędzy dwoma graczami (zwyczajowo Even oraz Odd) na grafie skierowanym G = (V, E). Gracze przesuwają między wierzchołkami wirtualny token, tworząc ścieżkę. Wierzchołki grafu są etykietowane liczbami naturalnymi i każdy z nich jest przypisany do jednego gracza, który decyduje w jakim kierunku zostanie wykonany ruch z tego wierzchołka. Celem każdego z graczy jest wybranie takiej strategii, że przy nieskończonej grze (ścieżce), najwyższa nieskończenie wiele razy powtarzająca się etykieta będzie odpowiednio parzysta bądź nieparzysta.

Problem gry parzystości jest deterministyczny, to znaczy dla każdego wierzchołka jeden z graczy posiada strategię wygrywającą. Rekurencyjny algorytm Zielonki rozwiązuje grę parzystości w czasie wykładniczym. Istnieje jednak algorytm działający w czasie quasi-wielomianowym, czyli 2O((log(n))^c) dla pewnego, ustalonego c.

W trakcie prezentacji omówiony zostanie schemat nowej wersji algorytmu, przeprowadzona analiza jego złożoności oraz przedstawiony dowód poprawności zwracanego przez niego wyniku.

27.11.2019 16:15
20.11.2019 16:15
Patryk Mikos
Theoretical computer science
Efficient enumeration of non-isomorphic interval graphs

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n4) time delay between the output of two consecutive graphs. We improve their algorithm and achieve O(n3 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).

27.11.2019 12:15
Piotr Mikołajczyk
Computer science foundations
Satisfiability in Strategy Logic can be Easier than Model Checking by Erman Acar, Massimo Benerecetti and Fabio Mogavero.

In the design of complex systems, model-checking and satisfiability arise as two prominent decision problems. While
model-checking requires the designed system to be provided in advance, satisfiability allows to check if such a system even exists. With very few exceptions, the second problem turns out to be harder than the first one from a complexity-theoretic standpoint. In this paper, we investigate the connection between the two problems for a non-trivial fragment of Strategy Logic (SL, for short). SL extends LTL with first-order quantifications over strategies, thus allowing to explicitly reason about the strategic abilities of agents in a multi-agent system. Satisfiability for the full logic is known to be highly undecidable, while model-checking is non-elementary.

The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important game-theoretic properties of multi-agent systems, such as existence of Nash and immune equilibria, as well as to formalize the rational synthesis problem. We show that satisfiability for such a fragment is PSPACE-COMPLETE, while its model-checking complexity is 2EXPTIME-HARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctive-binding first-order logic, a recently discovered decidable fragment of first-order logic.

21.11.2019 17:00
Adrian Siwiec
Combinatorial Optimization
Edge Coloring Signed Graphs

We define a method for edge coloring signed graphs and what it means for such a coloring to be proper. It then turns out that Vizing's Theorem is a special case of the more difficult theorem concerning signed graphs.

Richard Behr. Edge Coloring Signed Graphs. arXiv. 2018.

21.11.2019 16:15
Paweł Palenica
Combinatorial Optimization
Guess the Larger Number

We will discuss variations of a zero sum game where one player writes down two numbers on cards. The second player learns one of the numbers to make a guess which of the numbers is larger. We will show variations of the game where the second player has a greater chance of winning than 1/2.

Alexander Gnedin. Guess the Larger Number. arXiv. 2016.

21.11.2019 14:15
Jędrzej Kula, Przemysław Simajchel
Algorytmika
Subtree Isomorphism Revisited [A. Abboud et al.]

The Subtree Isomorphism problem asks whether a given tree is contained in an another given tree. The problem is of fundamental importance and has been studied since the 1960s. Subquadratic algorithms are known for some variants, e.g. ordered trees, but not in the general case.

We will present a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the SETH. In addition, we will show that the same lower bound holds even for the case of rooted trees of logarithmic height. To contrast the lower bound, we will also show subquadratic randomized algorithms for rooted trees of constant degree and logarithmic height.

The reductions utilize the new "tree gadgets" that are likely useful for future SETH-based lower bounds for problems on trees. The algorithms apply a folklore result from randomized decision tree complexity.

20.11.2019 12:15
Edyta Garbarz
Computer science foundations
Unifying Logical and Statistical AI Pedro by Domingos, Daniel Lowd, Stanley Kok, Aniruddh Nath, Hoifung Poon Matthew Richardson and Parag Singla
Intelligent agents must be able to handle the complexity and uncertainty of the real world. Logical AI has focused mainly on the former, and statistical AI on the latter. Markov logic combines the two by attaching weights to first-order formulas and viewing them as templates for features of Markov networks. Inference algorithms for Markov logic draw on ideas from satisfiability, Markov chain Monte Carlo and knowledge-based model construction. Learning algorithms are based on the voted perceptron, pseudo-likelihood and inductive logic programming. Markov logic has been successfully applied to a wide variety of problems in natural language understanding, vision, computational biology, social networks and others, and is the basis of the open-source Alchemy system.
13.11.2019 16:15
Grzegorz Guśpiel
Theoretical computer science
Smaller Universal Targets for Homomorphisms of Edge-Colored Graphs

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 Ω(kD(F)) and O(kd), where d is the ceiling of D(F) (result obtained in 2015 with Gutowski), and has been conjectured to be ϴ(kD(F)).

In this talk, I will present a construction of a k-universal graph on O(kd) 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 ϴ(kD(F)).

13.11.2019 12:15
Jan Kościsz
Computer science foundations
Bohm's Theorem, Church's Delta, Numeral Systems, and Ershov Morphisms by Richard Statman and Henk Barendregt
In this note we work with untyped lambda terms under beta-conversion and consider the possibility of extending Bohm's theorem to infnite RE (recursively enumerable) sets. Bohm's theorem fails in general for such sets V even if it holds for all fnite subsets of it. It turns out that generalizing Bohm's theorem to infnite sets involves three other superfcially unrelated notions; namely, Church's delta, numeral systems, and Ershov morphisms. Our principal result is that Bohm's theorem holds for an infnite RE set V closed under beta conversion iff V can be endowed with the structure of a numeral system with predecessor iff there is a Church delta (conditional) for V iff every Ershov morphism with domain V can be represented by a lambda term
07.11.2019 16:15
Kamil Rajtar
Combinatorial Optimization
A Price-Based Iterative Double Auction for Charger Sharing Markets

Jie Gao, Terrence Wong, Chun Wang, and Jia Yuan Yu. A Price-Based Iterative Double Auction for Charger Sharing Markets. arXiv. 2019.

07.10.2019 14:15
Nicoll Bryła, Mateusz Pabian
Algorytmika
Faster Algorithms for All Pairs Non-Decreasing Paths Problem [Duan, Jin, Wu]
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time Õ(n^((3+ω)/2)) = Õ(n^2,686). Here n is the number of vertices, and ω < 2.373 is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for (max, min)-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for (max, min)-matrix product. The previous best upper bound for APNP on weighted digraphs was Õ(n^(1/2(3+(3-ω)/(ω+1) + ω))) = Õ(n^2,78) [Duan, Gu, Zhang 2018]. We also show an Õ(n^2) time algorithm for APNP in undirected graphs which also reaches optimal within logarithmic factors.
06.11.2019 12:15
Rafał Burczyński
Computer science foundations
Compaction of Church Numerals by Isamu Furuya and Takuya Kida
In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number n, we prove that the size of the lambda term obtained by the proposed method is O((s log2n)^(log n/ (log log n))). Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when n is less than approximately 10,000 .
30.10.2019 16:15
Bartosz Walczak
Theoretical computer science
Coloring and Maximum Weight Independent Set of rectangles

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(ω2) 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.

30.10.2019 12:15
Jan Mełech
Computer science foundations
On compressing and indexing repetitive sequences by Sebastian Kreft and Gonzalo Navarro
We introduce LZ-End, a new member of the Lempel–Ziv family of text compressors, which achieves compression ratios close to those of LZ77 but is much faster at extracting arbitrary text substrings. We then build the first self-index based on LZ77 (or LZ-End) compression, which in addition to text extraction offers fast indexed searches on the compressed text. This self-index is particularly effective for representing highly repetitive sequence collections, which arise for example when storing versioned documents, software repositories, periodic publications, and biological sequence databases.
24.10.2019 16:15
Vladyslav Rachek
Combinatorial Optimization
On Chromatic Number of Exact Distance Graphs

For any graph G and positive integer p we can consider "exact distance graph" G in which vertices x and y are connected if and only if their distance in G is exactly p. We can bound chromatic number of such graphs using notion of weak coloring numbers. Proof becomes particularly valuable for odd p and planar graphs G.

Jan van den Heuvel, H.A. Kierstead, Daniel A. Quiroz. Chromatic Numbers of Exact Distance Graphs. arXiv, abs/1612.02160. 2016.

23.10.2019 16:15
Gwenaël Joret
Université Libre de Bruxelles
Theoretical computer science
A new proof of the Erdős-Pósa theorem with applications

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.

23.10.2019 12:15
Rafał Byczek
Computer science foundations
Suffix array and Lyndon factorization of a text by Sabrina Mantaci, Antonio Restivo, Giovanna Rosone and Marinella Sciortino
The main goal ofthis paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15]that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we propose sorts the suffixes by starting from the leftmost Lyndon factors, even if the whole text or the complete Lyndon factorization are not yet available.
17.10.2019 16:15
Vladyslav Rachek
Combinatorial Optimization
Steinberg's conjecture is false

It's commonly known that planar graphs are at most 4-colorable. One possible direction towards determining when planar graphs can be 3-colorable is to narrow to particular planar graphs with enforced structure. For example, one can forbid cycles of length 4,5,...,k where k>=4. There is a conjecture of Steinberg from 1976, that planar graphs without cycles of length 4 and 5 (as subgraphs) are 3-colorable. It has been open problem till 2016, when it was disproved in joint paper of Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado, and we present proof from that paper.

Steinberg's Conjecture is false. Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado. arXiv, abs/1604.05108. 2016.

17.10.2019 14:15
Piotr Helm, Krzysztof Zysiak
Algorytmika
Optimal Sorting with Persistent Comparison Errors [B. Geissmann et al.]
We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated. Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Ω(log n) and Ω(n), respectively, regardless of its running time.
In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Ω(n log n) time is necessary to guarantee such dislocation bounds.
In order to achieve this optimal result, we solve two sub-problems, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted.
16.10.2019 16:15
Mikkel Abrahamsen
Københavns Universitet
Theoretical computer science
Geometric Multicut

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(n4 log3n)-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.

16.10.2019 12:14
Maciej Nemś
Computer science foundations
Generating Random Well-Typed Featherweight Java Programs Using Quick Check by Samuel da Silva Feitosaa, Rodrigo Geraldo Ribeirob and Andre Rauber Du Bois
Currently, Java is one of the most used programming language, being adopted in many large projects, where applications reach a level of complexity for which manual testing and human inspection are not enough to guarantee quality in software development. Even when using automated unit tests, such tests rarely cover all interesting cases of code, which means that a bug could never be discovered, once the code is tested against the same set of rules over and over again. This paper addresses the problem of generating random well-typed programs in the context of Featherweight Java, a well-known object-oriented calculus, using QuickCheck, a Haskell library for property-based testing.
10.10.2019 16:15
Bartłomiej Bosek
Combinatorial Optimization
Majority choosability of digraphs

One of the variations of graph coloring is the assignment of colors to vertices such that for each v vertex, at most half of the neighbors v have the same color as v. Such coloring is called the majority coloring of the graph. The goal is to color the graph in the above way with the smallest number of colors. During the presentation various variants of this problem will be discussed, historical results, the latest results, and still intriguing hypotheses. Among other things, the effects of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24 (3), Paper 3.57, 2017.
  6. António Girão, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Šámal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15 – 20, 2019.
10.10.2019 14:15
Bartłomiej Jachowicz, Mateusz Kaczmarek
Algorytmika
Separating strings with small automata [J.M.Robson]

The main problem considered in this paper is to find the smallest finite automaton seperating two strings. Authors prove that, for strings of length bounded by n, there exists an automaton with O(n2/5 * log3/5n) states, accepting only one of given strings, which in the case of two strings with the same length is the best known result.

 

09.10.2019 12:15
Jacek Kurek
Computer science foundations
GENERIC ALGORITHMS FOR HALTING PROBLEM AND OPTIMAL MACHINES REVISITED
The halting problem is undecidable but can it be solved for "most" inputs? This natural question was considered in a number of papers, in diferent settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-Lof random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approximate versions of separation problems, and revisit Schnorr's results about optimal numberings showing how they can be generalized.
03.10.2019 16:15
Bartłomiej Bosek
Combinatorial Optimization
Choosability number of planar graphs

During the seminar, we will discuss some open problems regarding the choosability number of planar graphs and related problems.

19.06.2019 16:15
Bartłomiej Kielak
Theoretical computer science
Generalized Turán densities and counting cycles in graphs

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, C5, C3), 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, Ck, Ck−2) = (n/k)k + o(nk) for any odd k > 5.

Joint work with Andrzej Grzesik.

13.06.2019 17:00
Bruno Pitrus
Combinatorial Optimization
A Borsuk–Ulam Equivalent that Directly Implies Sperner’s Lemma

It is a known fact that Sperner's purely combinatorial lemma of triangulation is equivalent to theorems in the field of topology: Brouwer with a fixed point and Knastra-Kuratowski-Mazurkiewicz on covering the symplex. Both of these topological theorems have stronger versions (Borsuk-Ulam and Lusternik-Schnirelmann theorems on anti-inflammatory points). In the paper, the authors show a combinatorial analogue of Borsuk-Ulam theorem and use it to directly prove the Sperner lemma, closing the stronger trinity of theorems.

Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam Equivalent that Directly Implies Sperner's Lemma. The American Mathematical Monthly 120 (2017), no. 4, 346-354.

13.06.2019 16:15
Paweł Palenica
Combinatorial Optimization
Three famous theorems on finite sets

During the seminar I will present three statements about finite sets with evidence. Two of them are classic theorems of combinatorial power theory - theorems of Sperner and Erdős-Ko-Rado. The third of these is one of the most important theorems in finite set theory - the Hall theorem.

Martin Aigner, Günter M. Ziegler. Chapter 27 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

12.06.2019 16:15
Bartosz Walczak
Theoretical computer science
Subexponential algorithms for finding large induced sparse subgraphs

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 2o(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 Pt-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.

06.06.2019 16:15
Dominika Salawa
Combinatorial Optimization
The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs

In computer game 'Lemmings', lemmings are placed in a level walking towards certain direction. When they encounter a wall, they turn and walk back in the direction they came from and when they encounter a hole, they fall. If a lemming falls beyond a certain distance, it dies. The goal is to guide lemmings to the exit by assigning them skills and modifying their behavior. I will show by polynomial-time reduction from 3-SAT that deciding whether particular level is solvable is an NP-Complete problem. This holds even if there is only one lemming in the level to save.

Graham Cormode. The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs.

05.06.2019 12:14
Szymon Stankiewicz
Computer science foundations
Bohm's Theorem, Church's Delta, Numeral Systems, and Ershov Morphisms by Richard Statman and Henk Barendregt
In this note we work with untyped lambda terms under beta-conversion and consider the possibility of extending Bohm's theorem to in¯nite RE (recursively enumerable) sets. Bohm's theorem fails in general for such sets V even if it holds for all finite subsets of it. It turns out that generalizing Bohm's theorem to infnite sets involves three other superfcially unrelated notions; namely, Church's delta, numeral systems, and Ershov morphisms. Our principal result is that Bohm's theorem holds for an infnite RE set V closed under beta conversion iff V can be endowed with the structure of a numeral system withc predecessor iff there is a Church delta (conditional) for V iff every Ershov morphism with domain V can be represented by a lambda term.
04.06.2019 16:15
Jarosław Grytczuk
Politechnika Warszawska
Algorytmy Randomizowane i Aproksymacyjne
Graph polynomials and choosability
A result of Thomassen asserts that every planar graph is 5-choosable (colorable from arbitrary lists of size 5 preassigned to the vertices of a graph). We prove that every planar graph has a matching whose deletion gives a 4-choosable graph. The proof is based on Combinatorial Nullstellensatz - a famous algebraic result of Alon involving multivariable polynomials. We also discuss possible applications of this method to other graph coloring problems, like the four color problem or the empire coloring problem, for instance.
 
Joint work with Xuding Zhu.
29.05.2019 12:14
Bartłomiej Puget
Computer science foundations
Solving the Rubik’s Cube Optimally is NP-complete by Erik D. Demaine and Sarah Eisenstat
In this paper, we prove that optimally solving an n × n × n Rubik’s Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n×n×n Rubik’s Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik’s Square – an n × n × 1 generalization of the Rubik’s Cube – and then proceed with a similar but more complicated proof for the Rubik’s Cube case. Our results hold both when the goal is make the sides monochromatic and when the goal is to put each sticker into a specific location.
22.05.2019 12:14
Maciej Czerwiński
Computer science foundations
Automata Theoretic Account of Proof Search by Aleksy Schubert, Wil Dekkers and Henk P. Barendregt
Techniques from automata theory are developed that handle search for inhabitants in the simply typed lambda calculus. The resulting method for inhabitant search, which can be viewed as proof search by the Curry-Howard isomorphism, is proven to be adequate by a reduction of the inhabitant existence problem to the emptiness problem for appropriately defined automata. To strengthen the claim, it is demonstrated that the latter has the same complexity as the former. We also discuss the basic closure properties of the automata.
16.05.2019 17:00
Paweł Mader
Combinatorial Optimization
Probability makes counting (sometimes) easy

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

16.05.2019 16:15
Krzysztof Maziarz
Combinatorial Optimization
Exact Algorithms via Monotone Local Search

Parameterized algorithms can solve some optimization problems quickly, assuming a certain parameter is bounded: for example, when we aim to satisfy a SAT formula by setting at most k (out of n) variables to true. However, the same algorithms directly applied to the unbounded case (k = n) usually yield poor results. Here I will discuss a bridge between parameterized algorithms and general exact exponential-time algorithms. I will show a remarkably simple approach to obtaining a good exact exponential-time algorithm, given a good parameterized algorithm. The resulting algorithm will be randomized, but it is also possible to derandomize it with subexponential additional cost in the complexity. This approach, at the time of publishing, pushed the state-of-the-art for many optimization problems.

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh. Exact Algorithms via Monotone Local Search. arXiv. 2015.

15.05.2019 16:15
Krzysztof Kleiner
Theoretical computer science
Range queries and counting triangles

Listing and counting triangles in sparse graphs are well-studied problems. For a graph with m edges, Björklund et al. gave an O(m1.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(m4/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(m1.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.

15.05.2019 12:14
Przemysław Rutka (Lublin)
Computer science foundations
Wybrane algorytmiczne zastosowania klasycznych wielomianów ortogonalnych
Klasyczne wielomiany ortogonalne, odpowiadające im klasyczne funkcje wagowe oraz ich własności znajdują wiele zastosowań w takich chociażby obszarach jak tomografia, mechanika kwantowa, kombinatoryka, przetwarzanie obrazów i sygnałów, kompresja danych oraz zwiększanie wydajności algorytmów. W tym ostatnim zakresie cały czas uzyskuje się wiele ciekawych wyników, pozwalających na efektywne numeryczne rozwiązywanie różnych problemów. Można do tych problemów w szczególności zaliczyć barycentryczne interpolacje Fejéra, Hermite'a i Lagrange'a oraz problemy ekstremalne typu Szegő i Markowa-Bernsteina. W pierwszym przypadku, gdy interpolowanych jest n wartości w węzłach, będących zerami klasycznych wielomianów ortogonalnych, możliwa jest poprawa złożoności obliczeniowej algorytmów, obliczających wartości wielomianów interpolacyjnych w oparciu o wzory barycentryczne, z O(n^2) do O(n). Wymagane jest w tym celu zastosowanie odpowiednich jawnych wzorów na wagi barycentryczne lub wzorów wiążących wagi barycentryczne z wagami i węzłami kwadratur Gaussa. Z kolei w drugim przypadku, jak się okazuje powiązanym z pierwszym, daje się sformułować wzory, pozwalające bezpośrednio obliczać na komputerze najlepsze stałe, występujące w nierównościach typu Szegő i Markowa-Bernsteina oraz wartości wielomianów ekstremalnych, dla których te nierówności stają się równościami. Nierówności te związane są z iterowanymi klasycznymi funkcjami wagowymi i można je wykorzystać do szacowania wartości lub norm pochodnych D^{k}p lub różnic progresywnych Δ^{k}p wielomianów p(x), odpowiednio w przypadku ciągłym lub dyskretnym.
     Inne tego typu rezultaty, korzystające z klasycznych wag i/lub klasycznych wielomianów ortogonalnych, można otrzymać także dla problemu typu izoperymetrycznego w klasie płaskich, zamkniętych krzywych wielomianowych, problemu równowagi elektrostatycznej układu ładunków, problemu efektywnej, stabilnej i najbardziej ekonomicznej interpolacji oraz problemu dwustronnych oszacowań aproksymacyjnych a priori typu Chernoffa.
09.05.2019 17:00
Anita Badyl
Combinatorial Optimization
A Simplification of the MV Matching Algorithm and its Proof

Simple and effective algorithms solving the problem of finding maximum matchings in bipartite graphs had been known for years before a low-complexity algorithm for non-bipartite graphs was published for the first time. That algorithm is known as the Micali-Vazirani algorithm, and it constitutes an intricate combination of the Hopcroft-Karp algorithm for bipartite graphs and the Blossom algorithm for general graphs. It achieves the complexity of O(m√n), which demonstrates that matchings in general graphs are not harder to find than matchings in bipartite ones. We present an intuitive introduction to the algorithm, explaining its main definitions and procedures.

Vijay V. Vazirani. A Simplification of the MV Matching Algorithm and its Proof. arXiv. 2012.

09.05.2019 16:15
Kamil Rajtar
Combinatorial Optimization
Rectangular tiling

During the seminar will be presented proofs of the seemingly geometrical problem of tiling a rectangle with tiles with at least one side of total length.

Martin Aigner, Günter M. Ziegler. Chapter 26 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

08.05.2019 12:14
Weronika Grzybowska
Computer science foundations
A Mesh of Automata by Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, Rogerio Reis
We contribute new relations to the taxonomy of di erent conversions from regular expressions to equivalent nite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (A_POS), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version of the position automaton which plays a similar role as A_POS but now for the reverse expression. Moreover, it turns out that the prefix automaton A_Pre is central to reverse expressions, because the determinisation of the double reversal of A_Pre (first reverse the expression, construct the automaton A_Pre, and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to nite automata seems quite similar, there are signifcant differences.
25.04.2019 17:00
Michał Stobierski
Combinatorial Optimization
How 'hard' a video game can be?

Computer games are a well-studied branch of the theory of complexity. Many of them fit into a similar scheme, lying in the NP (and even NP-hard) and, thanks to Savitch's Theorem, in PSPACE (-hard). It turns out, however, that some of them, thanks to their unique mechanics, are able to simulate the operation of the Turing Machine and thus pose undecidable problems! An interesting example of such a game is Braid, on which this presentation is based. We will start by showing differences and similarities with other games, then we will show how to simulate the operation of the abstract 'counter machine' and talk about a particularly interesting variant of the game, which introduces an TM model that, when it writes to the tape, deletes all data on the tape to the right of the head. And despite the fact that it looks like simplified variant, it lies in EXPSPACE, making Braid a totally 'non-schematic' game.

25.04.2019 16:15
Rafał Byczek
Combinatorial Optimization
The chromatic number of Kneser graphs

In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a brilliant and totally unexpected solution, using the “Borsuk–Ulam theorem” from topology, was found by László Lovász twenty-three years later. It happens often in mathematics that once a proof for a long-standing problem is found, a shorter one quickly follows, and so it was in this case. Within weeks Imre Bárány showed how to combine the Borsuk–Ulam theorem with another known result to elegantly settle Kneser’s conjecture. Then in 2002 Joshua Greene, an undergraduate student, simplified Bárány’s argument even further, and it is his version of the proof that I present here.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

24.04.2019 16:15
Bartłomiej Bosek
Theoretical computer science
Algorithms for posets and graphs games – coloring and matching

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.

24.04.2019 14:00
Bartłomiej Jachowicz, Mateusz Kaczmarek
Algorytmika
On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree (M. Equi et al.)
Exact pattern matching in labeled graphs is the problem of searching paths of a graph G = (V, E) that spell the same string as the pattern P[1…m]. This problem can be solved in quadratic O(|E|m) time. In this paper authors give  a simple conditional lower bound that, for  any constant e > 0 an O(m |E|1-e) or O(|E| m1-e) time algorithm cannot be achieved unless Strong Exponential Time Hypothesis (SETH) is false.
17.04.2019 16:15
10.04.2019 16:15
Tomasz Krawczyk
Theoretical computer science
Testing isomorphism of circular-arc graphs - Hsu's approach revisited
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in a circular-arc graph and can be seen as its canonical representations; in particular, every intersection model can be easily transformed into a normalized one.

Our work adapts and appropriately extends the previous work on similar topic done by Hsu [SIAM J. Comput. 24(3), 411--439, (1995)]. In his work Hsu developed decomposition trees representing the structure of all normalized models of circular-arc graphs. However, due to the counterexample given in [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] his decomposition trees can not be used by the algorithm testing isomorphism of circular-arc graphs.
 
17.04.2019 14:00
Rafał Kaszuba, Michał Zwonek
Algorytmika
A simpler implementation and analysis of Chazelle’s Soft Heaps (H. Kaplan, U. Zwick)
Chazelle (2000) devised an approximate meldable priority queue data  structure, called Soft Heaps, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If n elements are inserted into a collection of soft heaps, then up to εn of the elements still contained in these heaps, for a given error parameter ε, may be corrupted, i.e.,have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in O(log 1/ε) amortized time. Chazelle’s soft heaps are derived from the binomial heaps data structure in which each priority queue is composed of a collection of binomial trees. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard binary trees. Our implementation has the advantage that no clean-up operations similar to the ones used in Chazelle’s implementation are required.We also present a concise and unified potential-based amortized analysis of the new implementation.
17.04.2019 12:14
Dawid Tracz
Computer science foundations
Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables by Iovka Boneva, Joachim Niehren, and Momar Sakho
We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on Xml streams with references.
11.04.2019 17:00
Filip Bartodziej
Combinatorial Optimization
Turán’s graph theorem

We’ll cover the Turan theorem from 1941, which provides a restriction on the number of edges in a graph that doesn’t contain an induced k-clique, depending on parameter k.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

11.04.2019 16:15
Mateusz Pabian
Combinatorial Optimization
Gaming is a hard job, but someone has to do it!

General schemes relating the computational complex-ity of a video game to the presence of certain common elements or mechan-ics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Proofs of complexity of several video games, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft.

Giovanni Viglietta. Gaming is a hard job, but someone has to do it! arXiv. 2013.

10.04.2019 12:14
Jan Derbisz
Computer science foundations
What Percentage of Programs Halt? by Laurent Laurent Bienvenu, Damien Desfontaines and Alexander Shen
Fix an optimal Turing machine U and for each n consider the ratio \rho^U_n of the number of halting programs of length at most n by the total number of such programs. Does this quantity have a limit value? In this paper, we show that it is not the case, and further characterise the reals which can be the limsup of such a sequence \rho^U_n . We also study, for a given optimal machine U, how hard it is to approximate the domain of U from the point of view of coarse and generic computability.
04.04.2019 17:00
Marcin Briański
Combinatorial Optimization
A short story of graphs that count

In 1978 Thomason provided a simple, constructive proof of Smith’s theorem; in particular this proof provides a simple algorithm enables one to find a second Hamiltonian cycle whenever one is given a cubic graph and a Hamiltonian cycle in it. For a couple of years, the runtime of the algorithm remained unknown, with worst known cases being cubic (in the number of vertices), however in 1999 Krawczyk found an example of a graph family, such that Thomason’s algorithm takes time Ω(2n/8) where is the number of vertices in the input graph from the family.

In this talk, I will present a family of cubic, planar, and 3-connected graphs, such that Thomason’s algorithm takes time Θ(1.1812n) on the graphs in this family. This scaling is currently the best known.

04.04.2019 16:15
Mateusz Tokarz
Combinatorial Optimization
The Slope Problem
28.03.2019 17:00
Vladyslav Hlembotskyi
Combinatorial Optimization
The Angel of power 2 wins

Let's consider the following game: we have two players (they are called the angel and the devil) and an infinite chessboard. The angel is located in some cell on the board. Players make moves alternatively. The devil chooses any cell that is not occupied by the angle and blocks it. The angel can jump to any other cell which is at distance at most p (p is fixed) from its present location and is not blocked. The devil wins if the angel cannot jump to any other cell. The angel wins if it can avoid being captured forever. We will show that the angel of power 2 has a winning strategy.

András Máthé. The Angel of power 2 wins. Combinatorics, Probability and Computing 16 (2007), no. 3, 363–374.

28.03.2019 16:15
Katarzyna Bułat
Combinatorial Optimization
Distributed tracing

The presentation will cover the topic of distributed tracing, which is an important issue in the field of distributed systems. Services are nowadays implemented as complex networks of related sub-systems and it is often hard to determine the source of performance problem in such complex structures. We will take a look at Dapper, a large-scale distributed systems tracing infrastructure, and discuss the challenges its designers had to face, as well as the opportunities the tool gives to programmers. We will discuss the core goals of effective instrumentation, analyze the problem of handling huge amount of tracing data and focus on security concerns.

21.03.2019 16:15
Adrian Siwiec
Combinatorial Optimization
Online Maximum Matching with Recourse

Online maximum matching problem has a recourse of k, when the decision whether to accept an edge to a matching can be changed k times, where k is typically a small constant. First, we consider the model in which arriving edge never disapears. We show that greedy algorithm has competitive ratio of 3/2 for even k and 2 for odd k. Then we show an improvement for typical values of k and proceed to show a lower bound of 1+1/(k-1). Later, we discuss a model where edges can appear and disappear at any time and show generalized algorithms.

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. arXiv. 2018.

20.03.2019 12:14
Rafał Byczek
Computer science foundations
Improving the Upper Bound on the Length of the Shortest Reset Words by Marek Szykula
We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than 114n^3 / 685+O(n^2). The Cerny conjecture states that (n−1)^2 is an upper bound. So far, the best general upper bound was (n^3−n)/6−1 obtained by J.-E. Pin and P. Frankl in 1982. Despite a number of efforts, it remained unchanged for about 35 years.
To obtain the new upper bound we utilize avoiding words. A word is avoiding for a state q if after reading the word the automaton cannot be in q. We obtain upper bounds on the length of the shortest avoiding words, and using the approach of Trahtman from 2011 combined with the well-known Frankl theorem from 1982, we improve the general upper bound on the length of the shortest reset words. For all the bounds, there exist polynomial algorithms finding a word of length not exceeding the bound.
14.03.2019 16:15
Bartłomiej Bosek
Combinatorial Optimization
Open problem session

At the seminar were presented some interesting open problems in the field of graph theory.

13.03.2019 14:15
Kornel Dulęba, Jan Mełech
Algorytmika
A Randomized Maximum-Flow Algorithm (Cheriyan & Hagerup)
A randomized algorithm for computing a maximum flow is presented. For an n-vertex m-edge network, the running time is O(nm + n2(log n)2) with probability at least 1 - 2-sqrt(nm). The algorithm is always correct, and in the worst case runs in O(nm log n) time. The only use of randomization is to randomly permute the adjacency lists of the network vertices at the start of the execution.