Seminars
22.03.2018 16:15 Aleksandra Mędrek 
Combinatorial Optimization The Matching Problem in General Graphs is in QuasiNC 
Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in QuasiNC, FOCS 2017 
28.03.2018 12:00 Szymon Stankiewicz 
Computer science foundations Introduction to HigherOrder Categorical Logic  continuation 
28.03.2018 16:15 Grzegorz Guśpiel 
Theoretical computer science On the Complexity of Crossing Minimization 
For a bipartite graph G with vertex bipartition (X, Y), a twolayer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines L_{X} and L_{Y}, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a twolayer drawing is a twolayered graph. We study basic graph problems on twolayered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.
This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi. 
04.04.2018 12:14 Vladyslav Hlembotskyi 
Computer science foundations A graph theoretic approach to automata minimality by Antonio Restivo and Roberto Vaglica 
The paper presents a graphtheoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graphtheoretic terms. 
05.04.2018 16:15 Anna Kobak 
Combinatorial Optimization On treepartitionwidth 
11.04.2018 12:14 Weronika Grzybowska 
Computer science foundations Average complexity of Moore’s and Hopcroft’s algorithms by Julien David 
In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore’s state minimization algorithm is O(n log (log n)), where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hopcroft’s algorithm is characterized, for which the algorithm will be proved to be always faster than Moore’s algorithm. Finally, we present experimental results on the usual implementations of Hopcroft’s algorithm. 
12.04.2018 16:15 Maciej Woźniak 
Combinatorial Optimization Find Your Place: Simple Distributed Algorithms for Community Detection 
18.04.2018 12:00 Rafał Burczyński 
Computer science foundations Mellin transforms and asymptotics 
We will introduce Mellin transform, which may be used for the asymptotic analysis of a particular class of sums. I will start with basic properties and then present fundamental correspondence between the asymptotic expansion of a function at 0 or infinity and singularities of its transform. Finally we will show some combinatorial applications of the transform. 
19.04.2018 16:15 Marcin Briański 
Combinatorial Optimization 
25.04.2018 12:00 Rafał Burczyński 
Computer science foundations How to select a loser 
Consider the following game: everyone from a group of n people flips a coin with result either 0 or 1, both equally probable; if no one gets a 0, the round is repeated, otherwise people with 1's are considered "winners" and the game continues only with participants who got 0's. The process continues until there is one person left, who is called "loser". We can picture this process as a binary tree and analyze some of its properties in average case. The analysis is not completely trivial, in particular one may find application for tools such as Mellin transform. 
25.04.2018 16:15 Jacek Krzaczkowski 
Theoretical computer science Complexity of solving equations 
26.04.2018 16:15 Sylwester Klocek 
Combinatorial Optimization 
09.05.2018 12:14 Dominika Salawa 
Computer science foundations The Hiring Problem and Permutations by Margaret Archibald and Conrado Martínez 
The hiring problem has been recently introduced by Broder et al. in last year’s ACMSIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem. 
10.05.2018 16:15 Jakub Szarawski 
Combinatorial Optimization Faster approximation schemes for the twodimensional knapsack problem 
16.05.2018 12:14 Maciej Czerwiński 
Computer science foundations On Type Inference in the Intersection Type Discipline by Gerard Boudol and Pascal Zimmer 
We introduce a new unification procedure for the type inference problem in the intersection type discipline. We show that unification exactly corresponds to reduction in an extended lambda calculus, where one never erases arguments that would be discarded by ordinary βreduction. We show that our notion of unification allows us to compute a principal typing for any strongly normalizing lambda expression. 
17.05.2018 16:15 Marcin Muszalski 
Combinatorial Optimization 
23.05.2018 12:14 Bruno Pitrus 
Computer science foundations Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger 
The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tuttestyle topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus. 
24.05.2018 16:15 Grzegirz Jurdziński 
Combinatorial Optimization Split Packing: An Algorithm for Packing Circles with Optimal WorstCase Density 
30.05.2018 12:14 Bartłomiej Puget 
Computer science foundations STATMAN'S HIERARCHY THEOREM by BRAM WESTERBAAN, BAS WESTERBAAN, RUTGER KUYPER, CARST TANKINK, REMY VIEHOFF AND HENK BARENDREGT 
In the Simply Typed lambda calculus Statman investigates the reducibility relation between types: for types freely generated using \arrow and a single ground type 0, define A \leq B if there exists a lambda definable injection from the closed terms of type A into those of type B. Unexpectedly, the induced partial order is the (linear) wellordering (of order type) \omega + 4.

30.05.2018 16:15 Grzegorz Herman 
Theoretical computer science TBA 
06.06.2018 12:14 Michał Zieliński 
Computer science foundations Lambda Theories allowing Terms with a Finite Number of Fixed Points by BENEDETTO INTRIGILA and RICHARD STATMAN 
A natural question in the lambda calculus asks what is the possible number of fixed points of a combinator (closed term). A complete answer to this question is still missing (Problem 25 of TLCA Open Problems List) and we investigate the related question about the number of fixed points of a combinator in lambda theories. We show the existence of a recursively enumerable lambda theory where the number is always one or infinite. We also show that there are lambda theories such that some terms have only two fixed points. In a first example this is obtained by means of a nonconstructive (more precisely nonRE) lambda theory where the range property is violated. A second, more complex example of a nonRE lambda theory (with a higher unsolvability degree) shows that some terms can have only two fixed points while the range property holds for every term. 
07.06.2018 16:15 Krzysztof Maziarz 
Combinatorial Optimization 
13.06.2018 12:14 Marcin Briański 
Computer science foundations COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS by DENIS HIRSCHFELDT, CARL JOCKUSCH, RUTGER KUYPER, AND PAUL SCHUPP 
A coarse description of a set A \subset \omega is a set D \subset \omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1random and B is computable from every coarse description D of A, then B is Ktrivial, which implies that if A is in fact weakly 2random then B is computable. Our main tool is a kind of compactness theorem for coneavoiding descriptions, which also allows us to prove the same result for 1 genericity in place of weak 2randomness. In the other direction, we show that if A \leq_T \emptyset is a 1random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all Ktrivial sets are computable from every coarse description of some 1random set.

14.06.2018 16:15 Mateusz Twaróg, Patryk Urbański 
Combinatorial Optimization Progress in the Arachne Project 
Poprzednie referaty
21.03.2018 12:00 Szymon Stankiewicz 
Computer science foundations Introduction to HigherOrder Categorical Logic by Lambec and Scott 
15.03.2018 16:15 Dawid Pyczek 
Combinatorial Optimization Punctured combinatorial Nullstellensätze 
14.03.2018 16:15 Michael Kompatscher Charles University in Prague 
Theoretical computer science CSPs of infinite structures and equations in oligomorphic algebras 
In 1998 Feder and Vardi famously conjectures that the constraint satisfaction problem (CSP) of a finite structure is either in P or NPcomplete. Universal algebra turned out to be the main tool in tackling their conjecture and lead to two recent proofs, showing that CSP(A) is in P if the polymorphism algebra associated with A is a Taylor algebra, and NPcomplete otherwise.
For CSPs of structures with infinite domains this universal algebraic approach fails badly in general. However, if the automorphism group of the structure is "sufficiently big", i.e. oligomorphic, many results can be transferred from the finite case. We survey results about the equational structure of oligomorphic algebras and their applications to constraint satisfaction problems. 
14.03.2018 12:14 Dawid Pyczek i Jakub Rówiński 
Computer science foundations Asymptotic Density and the Theory of Computability by CARL JOCKUSCH AND PAUL SCHUPP 
The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few easy proofs to illustrate the flavor of the subject. In complexity theory, classes such as P and NP are defined by using worstcase measures. That is, a problem belongs to the class if there is an algorithm solving it which has a suitable bound on its running time over all instances of the problem. Similarly, in computability theory, a problem is classified as computable if there is a single algorithm which solves all instances of the given problem. There is now a general awareness that worstcase measures may not give a good picture of a particular algorithm or problem since hard instances may be very sparse. The paradigm case is Dantzig’s Simplex Algorithm for linear programming problems. This algorithm runs many hundreds of times every day for scheduling and transportation problems, almost always very quickly. There are clever examples of Klee and Minty showing that there exist instances for which the Simplex Algorithm must take exponential time, but such examples are not encountered in practice. Observations of this type led to the development of averagecase complexity by Gurevich and by Levin independently. There are different approaches to the averagecase complexity, but they all involve computing the expected value of the running time of an algorithm with respect to some measure on the set of inputs. Thus the problem must be decidable and one still needs to know the worstcase complexity. Another example of hard instances being sparse is the behavior of algorithms for decision problems in group theory used in computer algebra packages. There is often some kind of an easy “fast check” algorithm which quickly produces a solution for “most” inputs of the problem. This is true even if the worstcase complexity of the particular problem is very high or the problem is even unsolvable. Thus many grouptheoretic decision problems have a very large set of inputs where the (usually negative) answer can be obtained easily and quickly. 
20.06.2018 12:15 Wojciech Szpankowski Purdue University USA 
Computer science foundations Analytic Information Theory: From Shannon to Knuth and Back 
08.03.2018 16:15 Jakub Rówiński 
Combinatorial Optimization On the 1/3–2/3 Conjecture 
Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an αbalanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams. Emily J. Olson, Bruce E. Sagan, On the 1/32/3 Conjecture, Order, 2018 
07.03.2018 12:14 Jarosław Duda Instytut Informatyki UJ 
Computer science foundations Some nonstandard approaches to hard computational problems 
I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm, compressed sensing, and the problem with global optimization formulations used in adiabatic
Slides: https://tinyurl.com/y74nx2t6 
01.03.2018 16:15 Bartłomiej Bosek 
Combinatorial Optimization Some open problems 
28.02.2018 16:15 Piotr Micek 
Theoretical computer science Seymour's conjecture on 2connected graphs of large pathwidth 
We prove the conjecture of Seymour (1993) that for every apexforest H1 and outerplanar graph H2 there is an integer p such that every 2connected graph of pathwidth at least p contains H1 or H2 as a minor. This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood. 
25.01.2018 16:15 Bartłomiej Bosek 
Combinatorial Optimization News about Combinatorial Nullstellensatz 
I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems. 
18.01.2018 16:15 Jarek Duda 
Combinatorial Optimization Some nonstandard approaches to hard computational problems 
I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subsetsum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem. Jarek Duda. Some unusualapproaches to hard computational problems. slides. 
17.01.2018 16:15 24.01.2018 16:15 Andrzej Dorobisz 
Theoretical computer science Online bipartite matching with amortized O(log²n) replacements 
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound. The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].
Based on the paper: Online bipartite matching with amortized O(log²n) replacements by Aaron Bernstein, Jacob Holm and Eva Rotenberg 
17.01.2018 12:00 Bartłomiej Puget i Dominika Salawa 
Computer science foundations Chapters 8.5  8.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
11.01.2018 16:15 Maciej Woźniak, Dawid Pyczek 
Combinatorial Optimization Online Vertex Cover and Matching: Beating the Greedy Algorithm 
Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal waterfilling algorithm with competitive ratio 1/(11/e) . The main contribution of this paper is a 1.901competitive algorithm for vertex cover in general graphs which beats the wellknown trivial 2competitive algorithm. The next major result is a primaldual analysis of given algorithm that implies the dual result of a 0.526competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs. 
10.01.2018 12:00 Kamil Rajtar 
Computer science foundations Chapters 8.1  8.4 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
04.01.2018 16:15 Grzegorz Bukowiec 
Combinatorial Optimization Feedback Vertex Set Problem 
A Feedback Vertex Set (FVS) is a subset of vertices in a graph such that its removal results in an acyclic graph. The problem of finding a minimal FVS is one of the classic NPcomplete problems. However, in some practical cases, we can assume that its size is fairly small. This motivated an intensive study of the parametrized version of this problem, which asks either for FVS of a size at most k or an information that it doesn't exist. There are several deterministic algorithms known which solve this in time O^{*}(c^{k}), the best one for now being O^{*}(3.592^{k}). 
03.01.2018 12:00 Dawid Pyczek i Jakub Rowiński 
Computer science foundations Chapters 7.6  7.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
21.12.2017 16:15 Paweł Kubiak, Jakub Rówiński 
Combinatorial Optimization Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms 
On bipartite graphs, problem of constrained minimum vertex cover (MINCVCB) is defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U ∪ L and two integers k_{u} and k_{l}, decide whether there is a minimum vertex cover in G with at most k_{u} vertices in U and at most k_{l} vertices in L. We show how it is related to practical problems. We prove that (MINCVCB) is NPcomplete. However, there are many parametrized algorithms running in decent time. We describe one of them, whereby linear kernelization method it achieves O(1.26^{ku+kl} +(k_{u} +k_{l})G) time. 
20.12.2017 16:15 Grzegorz Herman 
Theoretical computer science Declarative name resolution for complex, extensible languages 
We present a new, declarative, languageindependent model for name resolution, based on a data flow graph built using simple combinators. The model is expressive enough to capture complex name binding rules of modern programming languages (e.g., partial definitions, C++ argumentdependent lookup). It is also designed to make it straightforward toextend a language with new syntactic constructs, including new categories of names. The model, together with a proofofconcept resolution engine, has been implemented in Haskell, and evaluated on syntax trees of C# programs.
(This is joint work with Katarzyna Bułat.)

20.12.2017 12:00 Rafał Burczyński 
Computer science foundations Chapters 7.1  7.5 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
14.12.2017 17:00 Jakub Nowak 
Combinatorial Optimization Dulmage–Mendelsohn Decomposition 
In a graph G, let B be the set of vertices covered by every maximum matching in G, and let D = V(G) − B. Further partition B by letting A be the subset consisting of vertices with at least one neighbor outside B, and let C = B − A. The GallaiEdmonds Decomposition of G is the partition of V(G) into the three sets A, C, D. The Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is an extension of the GallaiEdmonds decomposition. L. Lovász, M. D. Plummer. Matching theory. NorthHolland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. NorthHolland Publishing Co., Amsterdam. 1986. pp. xxvii+544. ISBN: 0444879161. Chapter 4.3. 
14.12.2017 16:15 Lev Deliatynskyi 
Combinatorial Optimization A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem 
This paper studies the maximum matching in a graph. It shows a short proof of a BergeTutte formula and the GallaiEndmonds structure theorem. Authors use Hall's theorem to prove it. Deficiency in a graph (def(S), S⊆V(G)) is o(GS)  S, where o(GS) is the number of odd components in GS. BergeTutte formula says that the maximum size of a matching in an nvertex graph G is 1/2(ndef(G)), where def(G) = max_{S⊆V(G)}def(S). Gallai Edmonds has a sharper formulation which gives considerable information about the structure of maximum size matchings. 
13.12.2017 16:15 Tony Huynh Universite de Libre Bruxelles 
Theoretical computer science Strengthening Convex Relaxations of 0/1Sets using Boolean Formulas 
In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several generalpurpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semidefinite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization. 
13.12.2017 12:00 Katarzyna Grzybowska 
Computer science foundations Chapters 6.12  6.15 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
07.12.2017 16:15 Jan Derbisz, Franciszek Stokowacki 
Combinatorial Optimization On Low RankWidth Colorings 
We say that a class C of graphs admits low rankwidth colorings if there exist functions N : N → N and Q: N → N such that for all p ∈ N, every graph G ∈ C can be vertex colored with at most N(p) colors such that the union of any i ≤ p color classes induces a subgraph of rankwidth at most Q(i). It turns out that for every graph class C of bounded expansion and every positive integer r, the class {G^{r} : G ∈ C} of rth powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rankwidth colorings. Additionally, every graph class admitting low rankwidth colorings is χbounded. 
06.12.2017 12:00 Katarzyna Bułat 
Computer science foundations Chapter 6.8  6.11 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
30.11.2017 16:15 Krzysztof Maziarz, Tomasz Wesołowski 
Combinatorial Optimization The Generalised Colouring Numbers on Classes of Bounded Expansion 
We introduce two classes of graphs  graphs with bounded expansion and nowhere dense graphs. These notions are a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, to name just a few classes which are studied extensively in combinatorial and computer science contexts. We also present generalized colouring numbers adm_{r}(G), col_{r}(G), and wcol_{r}(G) and show important applications in the theory of abovementioned classes of graphs. Finally, we prove that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of r, and show that it can be efficiently computed. 
29.11.2017 16:15 Adam Polak 
Theoretical computer science Open problems in algorithms and complexity 
During the talk I'll present several interesting open problems, including, but not limited to:

29.11.2017 12:00 Filip Bartodziej 
Computer science foundations Chapter 6.1  6.7 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
23.11.2017 16:15 Gabriel Jakóbczak 
Combinatorial Optimization Majority coloring games 
A vertex coloring of graph G satisfies the majority rule, if for each vertex v at most half of its neighbors receive the same color as v. A coloring which satisfies the majority rule is called majority coloring. We consider its game version. For given graph G and color set C two players, Alice and Bob, in alternating turns color vertices with respect to the majority rule. Alice wins when every vertex becomes colored, while goal for Bob is to create a vertex which cannot be colored with any color belonging to the set C without breaking the majority rule. Let µ_{g(G)} denote the least number of colors belonging to C for which Alice has winning strategy in game on graph G. We show that if the color set C is finite, there exists a graph G on which Bob has winning strategy. We prove also that for graphs with col(G) = 3 parameter µ_{g(G)} is still unbounded. 
22.11.2017 16:15 Patryk Mikos 
Theoretical computer science Online interval coloring for bounded length intervals 
Online interval coloring was studied by Kierstead and Trotter. They presented an algorithm with competitive ratio 3,and showed a construction which implies that there is no algorithm with competitive ratio strictly less than 3. However, their construction in asymptotic case requires intervals with possibly unbounded length. We are interested in a variant of the online interval coloring problem in which all intervals have lenght between 1 and L. We show that as L tends to infinity the asymptotic competitive ratio tends to 5/2. Moreover we show that for L=1+epsi there is no algorithm with competitive ratio less than 5/3 and for L=2+epsi there is no algotihm with competitive ratio less than 7/4. Finally, we want to know how the asymptotic competitive ratio changes as a function of L. 
22.11.2017 12:00 Michał Ziobro 
Computer science foundations Chapter 5 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
16.11.2017 16:15 Anna Kobak, Grzegorz Jurdziński 
Combinatorial Optimization The Erdős discrepancy problem  Part II 
Erdős discrepancy problem has waited for the solution for over 70 years until last year Terrence Tao, with a help of Polymath project, has published a paper with its solution. After having our friends given an introduction to the topic and shown the Fourier analytic reduction of the problem last week we will continue presenting the proof. It will include the proof of Elliottype conjecture and a sketch of how to apply a generalised BorweinChoiCoons analysis for the final steps of the main proof. Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2 (2016), pp. 120. 
15.11.2017 16:15 Tomasz Krawczyk 
Theoretical computer science Representation and coloring of partially ordered sets under conditions of incomplete information 
The purpose of my talk is to discuss several problems related to coloring and construction of appropriate representation for partially ordered sets (also posets) and graph classes derived from posets. In these problems, we will assume the following two scenarios: in the first scenario, an algorithm receives a poset element one after another. For each new element added, the algorithm takes an irrevocable decision (assigns a color or extends a current representation) just after this element is presented (algorithms that work under such conditions are called online). in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs. In the context of online algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of online coloring of incomparability graphs, and embedding posets into ddimentional space R^{d}. In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs. We focus our attention on:

15.11.2017 12:00 Hanna Palianytsia i Agnieszka Rabiej 
Computer science foundations Chapter 4.5  4.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
09.11.2017 16:15 Aleksandra Mędrek, Marcin Muszalski 
Combinatorial Optimization The Erdős discrepancy problem  Part I 
Erdős discrepancy problem had remained unresolved for more than 80 years. In 2015 Erdős theorem has been proofed by Terrence Tao. We present first part of his proof where he uses a Fourieranalytic reduction obtained as part of the Polymath5 project which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g. Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2, (2016), pp. 120. 
08.11.2017 12:00 Miron Ficek 
Computer science foundations Chapter 4 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
26.10.2017 16:15 Wojciech Kruk 
Combinatorial Optimization Randomized PrimalDual Analysis of RANKING for Online Bipartite Matching 
We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 11/e competitive for the online bipartite matching problem. The proof is via a randomized primaldual argument. Primaldual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a nontrivial randomized primaldual algorithm in which the dual constraints only hold in expectation. 
25.10.2017 16:15 Bartłomiej Bosek 
Theoretical computer science A Tight Bound for Shortest Augmenting Paths on Trees 
The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound.

25.10.2017 12:00 Jakub Czarnowicz 
Computer science foundations Chapter 3 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
19.10.2017 16:15 Sylwester Klocek 
Combinatorial Optimization Online bipartite matching made simple 
We examine the classic online bipartite matching problem studied by Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. Algorithm attempts to match online new vertices with edges. Such a decision, once made, is irrevocable. The objective is to maximize the size of the resulting matching. We will see a sketch of simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 − 1/e. B.E. Birnbaum, C. Mathieu. Online bipartite matching made simple. SIGACT News 39 (1), 8087, 2008. 
18.10.2017 12:00 Piotr Wójcik 
Computer science foundations Chapter 4 of Flajolet book "Complex Analysis, Rational and Meromorphic Asymptotic". 
12.10.2017 16:15 Zygmunt Łenyk 
Combinatorial Optimization Handwritten graph diagrams recognition 
Graph visualisation problem is well known and there are many solutions to it. The reverse process  graph recognition  has been disregarded so far. Such solution has wide applications  from scientific to didactic. This paper focuses on handwritten graphs. Objects do not necessarily have regular shapes and there might be a lot of noise. Using computer vision techniques, we recognize first vertices and then edges. The result of the algorithm is a list of edges and a generated graph visualisation. 
11.10.2017 12:00 Tomasz Kisielewski 
Computer science foundations Logic of Provability by George Boolosa 
Short presentantion of the book Logic of Provability by George Boolos. 
05.10.2017 16:15 Szymon Borak 
Combinatorial Optimization On some problems in planar graphs 
We give insight into competitive reachability for outerplanar graphs and also for other classes of graphs with bounded degree. Competitive reachability is a game where two players orient the edges of undirected graph G alternately until all edges of G have been oriented. One player wants to minimize the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. And the second want to maximize it. Furthermore we focus on harmonious coloring conjecture for outerplanar graphs and further attempts in this area. A harmonious coloring of a graph G is a proper vertex coloring of G in which every pair of colors appears on adjacent vertices at most once. The harmonious chromatic number, denoted by h(G), is the minimum number of colors in a harmonious coloring. Analogically we define harmonious edge coloring in which every pair of colors appears on incident edges at most once. The minimal number of color we denote by h'(G). The conjecture states that h(G)<=h'(G). Finally we tackle the hamiltonian cycles in grid graphs. Grid graph are finite vertex induced subsets of infinite lattice, composed from unitside squares, equilateral triangles or equilateral hexagons. Decide whether the grid graph has hamiltonian cycle is NPhard in general. 
04.10.2017 12:15 Tomasz Kisielewski 
Computer science foundations Logic of Provability by George Boolosa 
Short presentantion of the book Logic of Provability by George Boolos.

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

14.06.2017 16:15 Piotr Wójcik 
Theoretical computer science On the asymptotic density of valid sentences in firstorder logic about one binary relation 
This study arises from the following question: what is the proportion of tautologies of the given length n among the number of all FO relational sentences of length n? We investigate the simplest language with a fixed signature σ = {r}, where r is a binary relation symbol. The model with four logic symbols and an universal quantifier lead us to discover an unexpected result  the fraction of valid sentences is always greater than a fixed constant and therefore the density, if exists, is positive. The main theorem is derived from the analysis of structural properties of FO formulae, which themselves bear strict resemblance to structural properties of λterms. 
13.06.2017 14:15 Kamil Sałaś 
Cryptology Helios: Webbased OpenAudit Voting 
The talk is based on the paper by Ben Adida with the same title [1]. In addition, we recall ElGamal encryption scheme and zeroknwoledge proofs. Voting with cryptographic auditing, sometimes called openaudit voting, has remained, for the most part, a theoretical endeavor. In spite of dozens of fascinating protocols and recent groundbreaking advances in the field, there exist only a handful of specialized implementations that few people have experienced directly. As a result, the benefits of cryptographically audited elections have remained elusive. We present Helios, the first webbased, openaudit voting system. Helios is publicly accessible today: anyone can create and run an election, and any willing observer can audit the entire process. Helios is ideal for online software communities, local clubs, student government, and other environments where trustworthy, secretballot elections are required but coercion is not a serious concern. With Helios, we hope to expose many to the power of openaudit elections. References [1] Ben Adida, Helios: Webbased OpenAudit Voting, Proceedings of the 17th Conference on Security Symposium, 2008, pp. 335348 
07.06.2017 12:15 Jakub Nowak 
Computer science foundations Generic Complexity of Presburger Arithmetic by Alexander N. Rybalov 
Fischer and Rabin proved in that the decision problem for Presburger Arithmetic has at least double exponential worstcase complexity (for deterministic and nondeterministic Turing machines). In paper 4 a theory of genericcase complexity was developed, where algorithmic problems are studied on "most" inputs instead of set of all inputs. An interesting question rises about existing of more efcient (say, polynomial) generic algorithm deciding Presburger Arithmetic on some set of closed formulas of asymptotic density 1 (socalled generic set). We prove, however, that there is not even an exponential generic algorithm working correctly on a set of inputs which (socalled strongly generic set). 
01.06.2017 16:15 Wojciech Kruk, Piotr Kruk 
Combinatorial Optimization Ulam Sequences and Ulam Sets 
The Ulam sequence is given by a1=1,a2=2, and then, for n≥3, the element an is defined as the smallest integer that can be written as the sum of two distinct earlier elements in a unique way. This gives the sequence 1,2,3,4,6,8,11,13,16,…, which has a mysterious quasiperiodic behavior that is not understood. Ulam's definition naturally extends to higher dimensions: for a set of initial vectors {v1,…,vk}⊂ℝn, we define a sequence by repeatedly adding the smallest elements that can be uniquely written as the sum of two distinct vectors already in the set. The resulting sets have very rich structure that turns out to be universal for many commuting binary operations. We give examples of different types of behavior, prove several universality results, and describe new unexplained phenomena.

31.05.2017 16:15 Piotr Micek 
Theoretical computer science Ramsey Theory for Binary Trees and the Separation of Treechromatic Number from Pathchromatic Number 
We propose a Ramsey theory for binary trees and prove that for every rcoloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have treechromatic number at most 2 while the pathchromatic number is bounded. This construction resolves a problem posed by Seymour. Joint work with Fidel BarreraCruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter. 
31.05.2017 12:15 Grzegorz Bukowiec 
Computer science foundations The Undecidability of the Generalized Collatz Problem by Stuart A. Kurtz and Janos Simon 
The Collatz problem, widely known as the 3x + 1 problem, asks whether or not a certain simple iterative process halts on all inputs. In this paper, we build on work of J. H. Conway to show that a natural generalization of the Collatz problem is $PI^0_2$ complete. 
30.05.2017 14:15 Jan Derbisz 
Cryptology Subquadratic Greatest Common Divisor 
The binary algorithm is a variant of the Euclidean algorithm that performs well in practice. We present a quasilinear time recursive algorithm that computes the greatest common divisor of two integers by simulating a slightly modified version of the binary algorithm. The structure of the algorithm is very close to the one of the wellknown KnuthSchonhage fast gcd algorithm; although it does not improve on its O(M(n) log n) complexity, the description and the proof of correctness are significantly simpler. This leads to a simplification of the implementation and to better running times. 
25.05.2017 16:15 Sylwester Klocek, Maciej Woźniak 
Combinatorial Optimization On the complexity of the chipfiring reachability problem 
In this paper, we study the complexity of the chipfiring reachability problem. We show that for Eulerian digraphs, the reachability problem can be decided in polynomial time, even if the digraph has multiple edges. We also show a special case when the reachability problem can be decided in polynomial time for general digraphs: if the target distribution is recurrent restricted to each strongly connected component. Both of these algorithms are strongly polynomial. As a further positive result, we show that the chipfiring reachability problem is in coNP for general digraphs. We also show that the chipfiring halting problem is in coNP for Eulerian digraph 
24.05.2017 12:15 Piotr Wójcik 
Computer science foundations Randombit optimal uniform sampling for rooted planar trees with given sequence of degrees and Applications by O.Bodini, J. David, and Ph. Marchal 
In this paper, we redesign and simplify an algorithm due to Remy et al. for the generation of rooted planar trees that satisfies a given partition of degrees. This new version is now optimal in terms of random bit complexity, up to a multiplicative constant. We then apply a natural process “simulateguessandproof” to analyze the height of a random Motzkin in function of its frequency of unary nodes. When the number of unary nodes dominates, we prove some unconventional height phenomenon. 
 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
 Szymon Borak
 Bartłomiej Bosek
 Iwona Cieślik
 Piotr Danilewski
 Andrzej Dorobisz
 Lech Duraj
 Adam Gągol
 Monika Gillert
 Katarzyna Grygiel
 Jarosław Grytczuk
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Leszek Horwath
 Pawel M. Idziak
 Piotr Kawałek
 Tomasz Kisielewski
 Karol Kosiński
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Łukasz Lachowski
 Wojciech Lubawski
 Agnieszka Łupińska
 Grzegorz Matecki
 Piotr Micek
 Patryk Mikos
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Michał Staromiejski
 Piotr Szafruga
 Maciej Ślusarek
 Bartosz Walczak
 Piotr Wójcik
 Michał Wrona
 Marek Zaionc
 Michał Zmarz
 Former colleagues