Seminars
23.10.2019 16:15 Gwenaël Joret Université Libre de Bruxelles 
Theoretical computer science A new proof of the ErdősPó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 vertexdisjoint cycles, or G has a set of 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. 
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 LZEnd, 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 selfindex based on LZ77 (or LZEnd) compression, which in addition to text extraction offers fast indexed searches on the compressed text. This selfindex 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. 
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 axisparallel rectangles in the plane with clique number ω has chromatic number Joint work with Parinya Chalermsook. 
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 . 
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 betaconversion 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 
13.11.2019 16:15 Grzegorz Guśpiel 
Theoretical computer science TBA 
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 firstorder 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 knowledgebased model construction. Learning algorithms are based on the voted perceptron, pseudolikelihood 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 opensource Alchemy system. 
20.11.2019 16:15 Patryk Mikos 
Theoretical computer science Efficient enumeration of nonisomorphic interval graphs 
21.11.2019 16:15 Paweł Palenica 
Combinatorial Optimization Guess the Larger Number 
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, modelchecking and satisfiability arise as two prominent decision problems. While 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 gametheoretic properties of multiagent 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 PSPACECOMPLETE, while its modelchecking complexity is 2EXPTIMEHARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctivebinding firstorder logic, a recently discovered decidable fragment of firstorder logic. 
04.12.2019 12:15 Michał Zwonek 
Computer science foundations Probably Half True: Probabilistic Satisfability over Lukasiewicz Infnitelyvalued Logic by Marcelo Finger and Sandro Preto 
We study probabilisticlogic reasoning in a context that allows for "partial truths", focusing on computational and algorithmic properties of nonclassical Lukasiewicz In nitelyvalued 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 NPcomplete class. An exact satis ability decision algorithm is presented which employs, as a subroutine, the decision problem for Lukasiewicz In nitelyvalued (non probabilistic) logic, that is also an NPcomplete problem. We develop implementations of the algorithms described and discuss the empirical presence of a phase transition behavior for those implementations. 
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 nonexpansive 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 bisimulationinvariant fragment of firstorder logic. Specifically, we show that every formula in probabilistic fuzzy firstorder logic that is nonexpansive wrt. behavioural distance can be approximated by concepts of bounded rank in probabilistic fuzzy description logic. 
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. 
19.12.2019 16:15 Filip Bartodziej 
Combinatorial Optimization How to eat 4/9 of a pizza 
Kolja Knauer, Piotr Micek, Torsten Ueckerdt. How to eat 4/9 of a pizza. arXiv. 2008. 
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 dISOMORPHISM DISTANCE (dID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomialtime solvable, and that the dISOMORPHISM DISTANCE problems generalize various classic rankaggregation 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. 
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 proofofconcept 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. 
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, SMotzkin and TMotzkin paths, are introduced. We provide bijections between SMotzkin paths and ternary trees, SMotzkin paths and noncrossing trees, and TMotzkin 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. 
Poprzednie referaty
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 subproblems, 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 almostsorted 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 kCut, where k is the number of different colors, as it can be seen as a geometric analogue to the wellstudied multicut problem on graphs. We first give an 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 WellTyped 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 welltyped programs in the context of Featherweight Java, a wellknown objectoriented calculus, using QuickCheck, a Haskell library for propertybased testing. 
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(n^{2/5} * log^{3/5}n) 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 MartinLof 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 In this talk, we will show an elementary proof that 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 KnastraKuratowskiMazurkiewicz on covering the symplex. Both of these topological theorems have stronger versions (BorsukUlam and LusternikSchnirelmann theorems on antiinflammatory points). In the paper, the authors show a combinatorial analogue of BorsukUlam theorem and use it to directly prove the Sperner lemma, closing the stronger trinity of theorems. 
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ősKoRado. The third of these is one of the most important theorems in finite set theory  the Hall theorem. 
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
This leads, for example, to the following corollaries for specific classes 𝒞 and 𝒟:
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 NPCompleteness 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 polynomialtime reduction from 3SAT that deciding whether particular level is solvable is an NPComplete 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 NPCompleteness 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 betaconversion 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 5choosable (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 4choosable 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 NPcomplete by Erik D. Demaine and Sarah Eisenstat 
In this paper, we prove that optimally solving an n × n × n Rubik’s Cube is NPcomplete 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 NPcomplete. 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 CurryHoward 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 
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 exponentialtime algorithms. I will show a remarkably simple approach to obtaining a good exact exponentialtime 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 stateoftheart for many optimization problems. 
15.05.2019 16:15 Krzysztof Kleiner 
Theoretical computer science Range queries and counting triangles 
Listing and counting triangles in sparse graphs are wellstudied problems. For a graph with m edges, Björklund et al. gave an O(m^{1.408}) algorithm which can list up to m triangles. The exact exponent depends on the exponent omega in matrix multiplication, and becomes 4/3 if omega=2. Pătraşcu proved that an algorithm faster than O(m^{4/3}) would imply a subquadratic algorithm for 3SUM, which is considered unlikely. In our work we consider a variant of triangle problem asking to determine for every edge the number of triangles which contains that edge. We prove that this problem is no easier than listing up to m triangles, although it still admits an algorithm of the same O(m^{1.408}) complexity. We also propose a natural class of range query problems, including for example the following problem: given a family of ranges in an array, compute the number of inversions in each of them. We prove that all the problems in this class are equivalent, under onetopolylog 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 VassilevskaWilliams. 
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 MarkowaBernsteina. 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 MarkowaBernsteina 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 lowcomplexity algorithm for nonbipartite graphs was published for the first time. That algorithm is known as the MicaliVazirani algorithm, and it constitutes an intricate combination of the HopcroftKarp 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. 
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 wellstudied branch of the theory of complexity. Many of them fit into a similar scheme, lying in the NP (and even NPhard) 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 'nonschematic' 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 twentythree years later. It happens often in mathematics that once a proof for a longstanding 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. 
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
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 semiuni 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 firstfit 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 ZychPawlewicz. 
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(Em) time. In this paper authors give a simple conditional lower bound that, for any constant e > 0 an O(m E^{1e}) or O(E m^{1e}) 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 circulararc graphs  Hsu's approach revisited 
Circulararc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circulararc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circulararc graphs. Normalized models reflect the neighbourhood relation in a circulararc 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), 411439, (1995)]. In his work Hsu developed decomposition trees representing the structure of all normalized models of circulararc graphs. However, due to the counterexample given in [Discrete Math. Theor. Comput. Sci., 15(1), 157182, 2013] his decomposition trees can not be used by the algorithm testing isomorphism of circulararc 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 comparisonbased 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 cleanup operations similar to the ones used in Chazelle’s implementation are required.We also present a concise and unified potentialbased 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 kclique, depending on parameter k. 
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 complexity of a video game to the presence of certain common elements or mechanics, 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 PacMan, 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 Ω(2^{n/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 3connected graphs, such that Thomason’s algorithm takes time Θ(1.1812^{n}) 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. 
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 subsystems and it is often hard to determine the source of performance problem in such complex structures. We will take a look at Dapper, a largescale 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/(k1). Later, we discuss a model where edges can appear and disappear at any time and show generalized algorithms. 
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 wellknown 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 MaximumFlow Algorithm (Cheriyan & Hagerup) 
A randomized algorithm for computing a maximum flow is presented. For an nvertex medge network, the running time is O(nm + n^{2}(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. 
13.03.2019 12:14 Vladyslav Hlembotskyi 
Computer science foundations Upper Bounds for Standardizations and an Application by Hongwei Xi 
We present a new proof for the standardization theorem in lambdacalculus, which is largely built upon a structural induction on lambdaterms. We then extract some bounds for the number of betareduction steps in the standard betareduction sequence obtained from transforming a given betareduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of betareduction sequences from any given simply typed A 
07.03.2019 16:15 Kamil Kropiewnicki 
Combinatorial Optimization Identities versus bijections 
In 1740 Leonhard Euler began to work on counting partitions. It resulted in two fundamental papers in the field. Integer partitions have been an active field of study ever since, tackled by many including Srinivasa Ramanujan, Paul Erdős and Donald Knuth. We present a few beautiful proofs of identities using only basic generating functions and simple bijections. 
06.03.2019 16:15 Zoltán Lóránt Nagy Eötvös University & Alfréd Rényi Institute of Mathematics 
Theoretical computer science Triangles in line arrangements 
A widely investigated subject in combinatorial geometry, originating from Erdős, is the following: given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances, e.g., determine the maximum number of unit distances, the maximum number of minimum/maximum distances, the minimum number of distinct distances? This has been generalized in many directions by taking point sets in a certain (not necessarily Euclidean) metric space and studying the distribution of certain configurations — and a whole theory emerged. In this talk I propose the following problem variant: consider planar line arrangements of n lines, and determine the maximum number of unit/maximum/minimum area determined by these lines. We prove that the order of magnitude for the maximum occurrence of unit area lies between Joint work with Gábor Damásdi, Leo MartínezSandoval and Dániel T. Nagy. 
06.03.2019 12:14 Jan Derbisz, Pola Kyzioł, Krzysztof Maziarz, Jakub Nowak, Grzegorz Juzrdziński 
Computer science foundations Prezentacje prac magisterskich 
Jan Derbisz, Promotor: dr hab. Tomasz Krawczyk Pola Kyzioł, Promotor: dr hab. Tomasz Krawczyk Krzysztof Maziarz, Promotor: prof. dr hab. Jacek Tabor Jakub Nowak, Promotor: prof. dr hab. Jacek Tabor Grzegorz Jurdziński, Promotor: dr Piotr Micek 
27.02.2019 16:15 Michał Wrona 
Theoretical computer science Relational Width of FirstOrder Expansions of Homogeneous Graphs with Bounded Strict Width 
We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by firstorder expansions of countably infinite homogeneous graphs, that are, the structures firstorderdefinable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H. 
26.02.2019 16:15 Marcin Briański 
Algorytmy Randomizowane i Aproksymacyjne Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz) 
24.01.2019 16:15 Rafał Burczyński 
Combinatorial Optimization Basic properties of 3CCP graphs 
We will introduce a class of graphs called 3CCP, which contains graphs that are 3connected, cubic (3regular) and planar. It was shown by Tarjan that finding Hamiltonian cycle in a graph assuming these properties remains NPcomplete  we will show the reduction from 3SAT problem. After that we will present Smith's theorem about parity of number of Hamiltonian cycles containing given edge in cubic graphs and show elegant constructive proof using Thomason's lollipop method. After that we will show a class of graphs for which previous algorithm for finding second Hamiltonian cycle takes exponential number of steps. 
24.01.2019 14:00 Jan Derbisz, Franciszek Stokowacki 
Algorytmika An Equivalence Class for Orthogonal Vectors (L.Chen, R.Williams) 
The Orthogonal Vectors problem, asking whether any pair from n vectors is orthogonal, can be easily solved in O(n^{2} log n), however no algorithm faster than n^{2} is known. The authors show that OV is trulysubquadratic equivalent to several fundamental problems e.g. (ApxMinIP)  finding redblue pair of vectors that is kapproximation to the minimum/maximum inner product and (Approximate Bichrom.ℓpClosestPair)  approximation to the closest redblue pair of points. Above equivalence results hold as well in Data Structure setting, where we answer online queries. Also, introduced constructions allow new approximation algorithms for ApxMinIP and some MAXSAT instances. 
23.01.2019 16:15 Lech Duraj 
Theoretical computer science A subquadratic algorithm for Longest Common Increasing Subsequence 
The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated longest common subsequence (LCS). For LCIS, as well as for LCS, there is an O(n^{2}) algorithm and a SETHbased quadratic lower bound. Both the algorithm and the proof of the bound are, however, quite different for LCIS. For LCS, there is also the MasekPaterson O(n^{2}/log n) algorithm. Its technique (the 'four Russians trick') does not seem to work for LCIS in any obvious way, so a natural question arises: does any subquadratic algorithm exist for Longest Common Increasing Subsequence problem? We answer this question positively, presenting a O(n^{2}/log^{a}n) algorithm for some a>0. The algorithm is not based on memorizing small inputs (often used for logarithmic speedups, including LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences. 
23.01.2019 12:14 
Computer science foundations canceled 
17.01.2019 16:15 Adrian Siwiec 
Combinatorial Optimization List coloring of Latin Squares 
For each cell (i, j) of NxN square there is given a list C(i, j) of N colors. Can we choose a color for each cell in such a way that colors in each row and each column are distinct? 
17.01.2019 14:00 Katarzyna Bułat, Kamil Rajtar 
Algorytmika Correctness of constructing optimal alphabetic trees reviseted 
Prezentowana przez nas praca przedstawia nowe obserwacje, które pozwoliły autorom dowieść poprawności dwóch znanych algorytmów (HuTuckera i GarsiWachs) na konstrukcję optymalnych drzew utrzymujących porządek leksykograficzny. Omówimy uogólnioną wersję algorytmu GarsiWachs wraz z przejrzystym i łatwym do zilustrowania dowodem, który pomaga również w zrozumieniu podejścia HuTuckera. 
16.01.2019 16:15 Grzegorz Gutowski 
Theoretical computer science Entropy Compression for Acylic EdgeColorings 
Let G be a graph with maximum degree d. We show a randomized procedure that colors the edges of G so that:
Such a coloring is called an acylic edgecoloring of G. The minimum number of colors in an acyclic edge coloring of G is called the acylic index of G. It is conjectured that acylic index of G is at most d+2. We are able to prove that our coloring procedure succeeds for roughly 3.97d colors (improving on a previous result that used 4d colors). This is joint work with Jakub Kozik and Xuding Zhu. 
16.01.2019 12:14 Rafał Byczek i Paweł Mader 
Computer science foundations A theory of linear typings as flows on 3valent 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 groupvalued “flow” on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3valent 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 nowherezero flows) may then be reexamined 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 proofnets in linear logic and to bidirectional typing. 
15.01.2019 16:15 Marcin Briański 
Algorytmy Randomizowane i Aproksymacyjne Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz) 
10.01.2019 16:15 Kamil Kropiewnicki 
Combinatorial Optimization Shuffling cards 
What do the birthday paradox, the coupon collector problem and shuffling cards have in common? What does it mean for a deck of cards to be "random" or "close to random"? How long does one have to shuffle a deck of cards until it is random? In practical use cases, the question is not about the asymptote  it is about the exact numbers. 
10.01.2019 14:00 Bartłomiej Jachowicz, Mateusz Kaczmarek 
Algorytmika SETHbased Lower Bounds for Subset Sum and Bicriteria Path 
The main result of this paper is a tight reduction from kSAT to Subset Sum on dense instances, proving that Bellman's 1962 pseudopolynomial O*(T)  time algorithm for Subset Sum on n numbers and target T cannot be improved to time T^{1  e} * 2^{o(n)} for any e > 0, unless SETH fails. 
09.01.2019 12:14 Krzysztof Turowski Purdue University, USA 
Computer science foundations Compression of Dynamic Graphs Generated by a Duplication Model 
One of the important topics in the information theory of nonsequential random data structures such as trees, sets, and graphs is the question of entropy: how many bits on average are needed to describe the structure. Here we consider dynamic graphs generated by a duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We provide asymptotic formulas for entopies for both labeled and unlabeled versions of such graphs and construct compression algorithms matching these bounds up to two bits. Moreover, as a side result, we were able to derive asymptotic expansions of expected value of f(X) for functions of polynomial growth, when X has betabinomial distribution  which in turn allowed to obtain e.g. asymptotic formula the entropy for a Dirichletmultinomial distribution. 
08.01.2019 16:15 Bartosz Wodziński 
Algorytmy Randomizowane i Aproksymacyjne Algorithmic barriers from phase transitions (Dimitris Achlioptas, Amin CojaOghlan) 
03.01.2019 16:15 Kamil Rajtar 
Combinatorial Optimization Communication without errors 
Main aim of the lecture is the answer for Claude Shannon's question from 1956: "Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?" 
03.01.2019 14:00 Rafał Kaszuba, Krzysztof Zysiak 
Algorytmika Fast Modular Subset Sum using Linear Sketching 
Dostając zbiór n dodatnich liczb całkowitych, problem Modular Subset Sum polega na sprawdzeniu czy istnieje podzbiór, który sumuje się do zadanego t modulo dana liczba całkowita m. Jest to naturalne uogólnienie problemu Subset Sum (m=+∞), który silnie łączy się z addytywną kombinatoryką i kryptografią. Niedawno zostały opracowane efektywne algorytmy dla przypadku niemodularnego, działające w czasie bliskoliniowym pseudowielomianowym. Jednak dla przypadku modularnego najlepszy znany algorytm (Koiliaris'a i Xu) działa w czasie Õ(m^{5/4}). W tej pracy prezentujemy algorytm działający w czasie Õ(m), który dopasowuje się do warunkowego ograniczenia dolnego opartego na SETH. W przeciwieństwie do większości poprzednich wyników związanych z problemem Subset Sum, nasz algorytm nie korzysta z FFT. Natomiast, jest zdolny zasymulować "podręcznikowe" programowanie dynamiczne znacznie szybciej, używając pomysłów ze Szkicowania Liniowego. Jest to jedna z pierwszych aplikacji technik bazujących na szkicowaniu, by osiągnąć szybki algorytm dla problemów kombinatorycznych w modelu offline. 
 Home
 Algorithmics Research Group
 Foundations of Computer Science
 Faculty of Mathematics and Computer Science
 Contact
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Photos
 People
 Maciej Bendkowski
 Bartłomiej Bosek
 Iwona Cieślik
 Piotr Danilewski
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Łukasz Lachowski
 Agnieszka Łupińska
 Marcin Mazur
 Piotr Micek
 Patryk Mikos
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Maciej Ślusarek
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Former colleagues