# Seminars

 23.05.2018 12:14 Computer science foundations Canceled
 24.05.2018 16:15 Marcin Briański Combinatorial Optimization How many ants does it take to find the food? Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, Roger Wattenhofer, How many ants does it take to find the food?, Theoretical Computer Science Volume 608, Part 3, 10 December 2015, Pages 255-267
 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) well-ordering (of order type) \omega + 4.
 30.05.2018 16:15 Grzegorz Herman Theoretical computer science Relational parsing: a clean generalized parsing algorithm. We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.
 06.06.2018 12:14 Bruno Pitrus Computer science foundations Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.
 07.06.2018 16:15 Krzysztof Maziarz Combinatorial Optimization SeminariumOK
 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 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1- genericity in place of weak 2-randomness. In the other direction, we show that if A \leq_T \emptyset is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set.
 14.06.2018 16:15 Mateusz Twaróg, Patryk Urbański Combinatorial Optimization Progress in the Arachne Project

# Poprzednie referaty

 17.05.2018 16:15 Marcin Muszalski Combinatorial Optimization On the Number of Maximum Empty Boxes Amidst n Points I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S. They created first superlinear lower bound for the number of maximum-volume empty boxes amidst n points in R d (d ≥ 3). I would like to present it and show a prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log(n) 2^α(n) ), where α(n) is the extremely slowly growing inverse of Ackermann’s function. The previous best bound for this problem, O(n^2 ), is due to Naamad, Lee, and Hsu (1984). Adrian Dumitrescu, Minghui Jiang, On the Number of Maximum Empty Boxes Amidst n Points, Discrete & Computational Geometry, Volume 59 (3), 742-756, 2018
 16.05.2018 12:14 Maciej Czerwiński Computer science foundations On Type Inference in the Intersection Type Discipline by Gerard Boudol and Pascal Zimmer We introduce a new unification procedure for the type inference problem in the intersection type discipline. We show that unification exactly corresponds to reduction in an extended  lambda calculus, where one never erases arguments that would be discarded by ordinary β-reduction. We show that our notion of unification allows us to compute a principal typing for any strongly normalizing lambda expression.
 10.05.2018 16:15 Jakub Szarawski Combinatorial Optimization Faster approximation schemes for the two-dimensional knapsack problem In 2008 Klaus Jansen and Roberto Solis-Oba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented. S. Heydrich, A. Wiese, Faster approximation schemes for the two-dimensional knapsack problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 79-98
 09.05.2018 12:14 Dominika Salawa Computer science foundations The Hiring Problem and Permutations by Margaret Archibald and Conrado Martínez The hiring problem has been recently introduced by Broder et al. in last year’s ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem.
 26.04.2018 16:15 Sylwester Klocek Combinatorial Optimization Colouring of (P3∪P2)-free graphs In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs. Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)-free graphs, Graphs and Combinatorics, Volume 34 (1), 2018
 25.04.2018 16:15 Jacek Krzaczkowski Theoretical computer science Complexity of solving equations Solving equations  is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider  equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is  obviously decidable in nondeterministic polynomial time. The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on  the polynomial  equivalence problem in which we ask whether two polynomials over  a finite algebra describe the same function. This is joint work with Paweł M. Idziak and Piotr Kawałek..
 25.04.2018 12:00 Rafał Burczyński Computer science foundations How to select a loser Consider the following game: everyone from a group of n people flips a coin with result either 0 or 1, both equally probable; if no one gets a 0, the round is repeated, otherwise people with 1's are considered "winners" and the game continues only with participants who got 0's. The process continues until there is one person left, who is called "loser". We can picture this process as a binary tree and analyze some of its properties in average case. The analysis is not completely trivial, in particular one may find application for tools such as Mellin transform.
 19.04.2018 16:15 Grzegorz Jurdziński Combinatorial Optimization Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles. Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109
 18.04.2018 12:00 Rafał Burczyński Computer science foundations Mellin transforms and asymptotics We will introduce Mellin transform, which may be used for the asymptotic analysis of a particular class of sums. I will start with basic properties and then present fundamental correspondence between the asymptotic expansion of a function at 0 or infinity and singularities of its transform. Finally we will show some combinatorial applications of the transform.
 12.04.2018 16:15 Maciej Woźniak Combinatorial Optimization Find Your Place: Simple Distributed Algorithms for Community Detection Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if: G is connected and not bipartite, |V_1| = |V_2| V_1 \cap V_2 = \emptyset Every vertex has degree d Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1, Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2. We define (weak) block reconstruction of graph as two-coloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact. I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for non-regular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities. Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia
 11.04.2018 12:14 Weronika Grzybowska Computer science foundations Average complexity of Moore’s and Hopcroft’s algorithms by Julien David In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore’s state minimization algorithm is O(n log (log n)),  where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hopcroft’s algorithm is characterized, for which the algorithm will be proved to be always faster than Moore’s algorithm. Finally, we present experimental results on the usual implementations of Hopcroft’s algorithm.
 05.04.2018 16:15 Anna Kobak Combinatorial Optimization On tree-partition-width A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2. David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253
 04.04.2018 16:15 Bartosz Walczak Theoretical computer science Sparse Kneser graphs are Hamiltonian For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of {1, …, n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k + 1, k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥ 3, the odd graph K(2k + 1, k) has a Hamilton cycle. Its construction is based on constructing a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, it provides an alternative proof of the so-called middle levels theorem, originally proved by Mütze in 2014. Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636).
 04.04.2018 12:14 Vladyslav Hlembotskyi Computer science foundations A graph theoretic approach to automata minimality by Antonio Restivo and Roberto Vaglica The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
 28.03.2018 16:15 Grzegorz Guśpiel Theoretical computer science On the Complexity of Crossing Minimization For a bipartite graph G with vertex bipartition (X, Y), a two-layer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines LX and LY, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a two-layer drawing is a two-layered graph. We study basic graph problems on two-layered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)-path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.   This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi.
 28.03.2018 12:00 Szymon Stankiewicz Computer science foundations Introduction to Higher-Order Categorical Logic - continuation
 22.03.2018 16:15 Aleksandra Mędrek Combinatorial Optimization The Matching Problem in General Graphs is in Quasi-NC Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached. Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017
 21.03.2018 12:00 Szymon Stankiewicz Computer science foundations Introduction to Higher-Order Categorical Logic by Lambec and Scott
 15.03.2018 16:15 Dawid Pyczek Combinatorial Optimization Punctured combinatorial Nullstellensätze This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problem-solving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions. Simeon Ball, Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica, September 2009, Volume 29, Issue 5, pp 511–522
 14.03.2018 16:15 Michael Kompatscher Charles University in Prague Theoretical computer science CSPs of infinite structures and equations in oligomorphic algebras In 1998 Feder and Vardi famously conjectures that the constraint satisfaction problem (CSP) of a finite structure is either in P or NP-complete. Universal algebra turned out to be the main tool in tackling their conjecture and lead to two recent proofs, showing that CSP(A) is in P if the polymorphism algebra associated with A is a Taylor algebra, and NP-complete otherwise. For CSPs of structures with infinite domains this universal algebraic approach fails badly in general. However, if the automorphism group of the structure is "sufficiently big", i.e. oligomorphic, many results can be transferred from the finite case. We survey results about the equational structure of oligomorphic algebras and their applications to constraint satisfaction problems.
 14.03.2018 12:14 Dawid Pyczek i Jakub Rówiński Computer science foundations Asymptotic Density and the Theory of Computability by CARL JOCKUSCH AND PAUL SCHUPP The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few easy proofs to illustrate the flavor of the subject. In complexity theory, classes such as P and NP are defined by using worst-case measures. That is, a problem belongs to the class if there is an algorithm solving it which has a suitable bound on its running time over all instances of the problem. Similarly, in computability theory, a problem is classified as computable if there is a single algorithm which solves all instances of the given problem. There is now a general awareness that worst-case measures may not give a good picture of a particular algorithm or problem since hard instances may be very sparse. The paradigm case is Dantzig’s Simplex Algorithm for linear programming problems. This algorithm runs many hundreds of times every day for scheduling and transportation problems, almost always very quickly. There are clever examples of Klee and Minty showing that there exist instances for which the Simplex Algorithm must take exponential time, but such examples are not encountered in practice. Observations of this type led to the development of average-case complexity by Gurevich and by Levin independently. There are different approaches to the average-case complexity, but they all involve computing the expected value of the running time of an algorithm with respect to some measure on the set of inputs. Thus the problem must be decidable and one still needs to know the worst-case complexity. Another example of hard instances being sparse is the behavior of algorithms for decision problems in group theory used in computer algebra packages. There is often some kind of an easy “fast check” algorithm which quickly produces a solution for “most” inputs of the problem. This is true even if the worst-case complexity of the particular problem is very high or the problem is even unsolvable. Thus many group-theoretic decision problems have a very large set of inputs where the (usually negative) answer can be obtained easily and quickly.
 20.06.2018 12:15 Wojciech Szpankowski Purdue University USA Computer science foundations Analytic Information Theory: From Shannon to Knuth and Back
 08.03.2018 16:15 Jakub Rówiński Combinatorial Optimization On the 1/3–2/3 Conjecture Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an α-balanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2-balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams. Emily J. Olson, Bruce E. Sagan, On the 1/3--2/3 Conjecture, Order, 2018
 07.03.2018 12:14 Jarosław Duda Instytut Informatyki UJ Computer science foundations Some nonstandard approaches to hard computational problems I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm.  I will start with briefly explaining mechanism used in Shor algorithm, compressed sensing, and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem.  Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, geometric perspective on this problem, and some new approach to rotation invariants for this purpose.   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 2-connected graphs of large pathwidth We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor. This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood.
 25.01.2018 16:15 Bartłomiej Bosek Combinatorial Optimization News about Combinatorial Nullstellensatz I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems. Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. arXiv:1310.6482 (2014), pp 1-44.
 18.01.2018 16:15 Jarek Duda Combinatorial Optimization Some nonstandard approaches to hard computational problems I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem. Jarek Duda. Some unusualapproaches to hard computational problems. slides.
 17.01.2018 16:15 24.01.2018 16:15 Andrzej Dorobisz Theoretical computer science Online bipartite matching with amortized O(log²n) replacements In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound. The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].   Based on the paper: Online bipartite matching with amortized O(log²n) replacements by Aaron Bernstein, Jacob Holm and Eva Rotenberg
 17.01.2018 12:00 Bartłomiej Puget i Dominika Salawa Computer science foundations Chapters 8.5 - 8.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet
 11.01.2018 16:15 Maciej Woźniak, Dawid Pyczek Combinatorial Optimization Online Vertex Cover and Matching: Beating the Greedy Algorithm Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal water-filling algorithm with competitive ratio 1/(1-1/e) . The main contribution of this paper is a 1.901-competitive algorithm for vertex cover in general graphs which beats the well-known trivial 2-competitive algorithm. The next major result is a primal-dual analysis of given algorithm that implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs. Yajun Wang, Sam Chiu-wai Wong. Online Vertex Cover and Matching: Beating the Greedy Algorithm. arXiv (2013), pp 1-21.
 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 NP-complete 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*(ck), the best one for now being O*(3.592k).
 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 (MIN-CVCB) is defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U ∪ L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. We show how it is related to practical problems. We prove that (MIN-CVCB) is NP-complete. However, there are many parametrized algorithms running in decent time. We describe one of them, whereby linear kernelization method it achieves O(1.26ku+kl +(ku +kl)|G|) time. Jianer Chen, Iyad A.Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences. Vol. 67, Iss. 4, (2003), pp. 833-847.
 20.12.2017 16:15 Grzegorz Herman Theoretical computer science Declarative name resolution for complex, extensible languages We present a new, declarative, language-independent 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++ argument-dependent 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 proof-of-concept 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 Gallai-Edmonds 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 Gallai-Edmonds decomposition. L. Lovász, M. D. Plummer. Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam. 1986. pp. xxvii+544. ISBN: 0-444-87916-1. 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 Berge-Tutte formula and the Gallai-Endmonds structure theorem. Authors use Hall's theorem to prove it. Deficiency in a graph (def(S), S⊆V(G)) is o(G-S) - |S|, where o(G-S) is the number of odd components in G-S. Berge-Tutte formula says that the maximum size of a matching in an n-vertex graph G is 1/2(n-def(G)), where def(G) = maxS⊆V(G)def(S). Gallai Edmonds has a sharper formulation which gives considerable information about the structure of maximum size matchings. Douglas B.West. A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem. European Journal of Combinatorics. Vol. 32, Iss. 5, (2011), pp. 674-676.
 13.12.2017 16:15 Tony Huynh Universite de Libre Bruxelles Theoretical computer science Strengthening Convex Relaxations of 0/1-Sets 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 general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies.  On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches.  Our procedure strengthens any convex set containing a set of 0/1-points S, by exploiting certain additional information about S.  Namely, the required extra information will be in the form of a Boolean formula defining the target set S.  The strengthened relaxation is obtained by ''feeding'' the convex set into the formula defining S. As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems. This is joint work with Samuel Fiorini and Stefan Weltge.
 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 Rank-Width Colorings We say that a class C of graphs admits low rank-width 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 rank-width at most Q(i). It turns out that for every graph class C of bounded expansion and every positive integer r, the class {Gr : G ∈ C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. Additionally, every graph class admitting low rank-width colorings is χ-bounded. O-joung Kwon, Michał Pilipczuk, and Sebastian Siebertz. On Low Rank-Width Colorings. arXiv (2017), pp. 1-17.
 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 admr(G), colr(G), and wcolr(G) and show important applications in the theory of above-mentioned 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. Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Vol. 58 (2016), pp. 85:1-85:13.
 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: Conditional lower bounds for k-mismatch pattern matching Faster algorithms for subset sum Complexity of 3-coloring for graphs with excluded k-paths
 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 On-line interval coloring for bounded length intervals On-line interval coloring was studied by Kierstead and Trotter. They presented an algorithm with competitive ratio 3,and showed a construction which implies that there is no algorithm with competitive ratio strictly less than 3. However, their construction in asymptotic case requires intervals with possibly unbounded length. We are interested in a variant of the on-line interval coloring problem in which all intervals have lenght between 1 and L. We show that as L tends to infinity the asymptotic competitive ratio tends to 5/2. Moreover we show that for L=1+epsi there is no algorithm with competitive ratio less than 5/3 and for L=2+epsi there is no algotihm with competitive ratio less than 7/4. Finally, we want to know how the asymptotic competitive ratio changes as a function of L.
 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 Elliot-type conjecture and a sketch of how to apply a generalised Borwein-Choi-Coons analysis for the final steps of the main proof. Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2 (2016), pp. 1-20.
 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 on-line). in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs. In the context of on-line algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of on-line coloring of incomparability graphs, and embedding posets into d-dimentional space Rd. In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs. We focus our attention on: function graphs that are intersection graphs of continuous functions [0,1] → R, permutation graphs that are intersection graphs of linear functions [0,1] → R, trapezoid graphs that are intersection graphs of trapezoids spanned between two fixed parallel lines containing the bases of these trapezoids.
 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 Fourier-analytic 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. 1-20.
 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 Primal-Dual Analysis of RANKING for Online Bipartite Matching We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual 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 non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg. Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 101-107, SIAM, Philadelphia, PA, 2012.
 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=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound.
 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 On-line bipartite matching made simple We examine the classic on-line 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. On-line bipartite matching made simple. SIGACT News 39 (1), 80-87, 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 hand-written 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 unit-side squares, equilateral triangles or equilateral hexagons. Decide whether the grid graph has hamiltonian cycle is NP-hard 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 quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right. Based on the paper: Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić
 14.06.2017 16:15 Piotr Wójcik Theoretical computer science On the asymptotic density of valid sentences in first-order 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: Web-based Open-Audit Voting The talk is based on the paper by Ben Adida with the same title [1]. In addition, we recall ElGamal encryption scheme and zero-knwoledge proofs. Voting with cryptographic auditing, sometimes called open-audit voting, has remained, for the most part, a theoretical endeavor. In spite of dozens of fascinating protocols and recent ground-breaking 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 web-based, open-audit 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 on-line software communities, local clubs, student government, and other environments where trustworthy, secret-ballot elections are required but coercion is not a serious concern. With Helios, we hope to expose many to the power of open-audit elections. References [1] Ben Adida, Helios: Web-based Open-Audit Voting, Proceedings of the 17th Conference on Security Symposium, 2008, pp. 335-348
 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 worst-case complexity (for deterministic and nondeterministic Turing machines). In paper 4  a theory of generic-case 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 (so-called generic set). We prove, however, that there is not even an exponential generic algorithm working correctly on a set of inputs which (so-called 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 quasi-periodic 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. Noah Kravitz, Stefan Steinerberger Ulam Sequences and Ulam Sets
 31.05.2017 16:15 Piotr Micek Theoretical computer science Ramsey Theory for Binary Trees and the Separation of Tree-chromatic Number from Path-chromatic Number We propose a Ramsey theory for binary trees and prove that for every r-coloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have tree-chromatic number at most 2 while the path-chromatic number is bounded. This construction resolves a problem posed by Seymour. Joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter.
 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 quasi-linear 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 well-known Knuth-Schonhage 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 chip-firing reachability problem In this paper, we study the complexity of the chip-firing 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 chip-firing reachability problem is in co-NP for general digraphs. We also show that the chip-firing halting problem is in co-NP for Eulerian digraph