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.

28.02.2018 16:15
Piotr Micek
Theoretical computer science
15.03.2018 16:15
Jacek Krzaczkowski
Theoretical computer science
Complexity of solving equations
28.03.2018 16:15
Grzegorz Guśpiel
Theoretical computer science
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

Poprzednie referaty

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

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

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

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

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

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


[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.
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
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
24.05.2017 12:15
Piotr Wójcik
Computer science foundations
Random-bit 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 “simulate-guess-and-proof” 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
23.05.2017 14:15
Szymon Policht
Supersingular isogeny key exchange
Supersingular isogeny is the newest addition to the post-quantum cryptography roster. It is elliptic curve based, but unlike tradidional ECC algorithms, it's quantum resistant. It offers significant key size reduction and computation time speedup compared to other post-quantum algorithms.
18.05.2017 16:15
Katrzyna Janocha
Combinatorial Optimization
Proper Orientations of Planar Bipartite Graphs
An orientation of a graph G is proper if any two adjacent vertices have different indegrees. The proper orientation number χ (G) of a graph G is the minimum of the maximum indegree, taken over all proper orientations of G. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that χ (G) ≤ 4, when G is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.
16.05.2017 14:15

Dzień Magistranta (sala 0004)
11.05.2017 16:15
Anna Kobak
Combinatorial Optimization
Lambda number for the direct product of some family of graphs
An L(2,1) labeling for a graph G = (V,E) is a function f on V such that | f(u) - f(v)| >= 2 if u,v are adjacent and f(u), f(v) are distinct if u,v are vertices of distance two. The lambda(G) for G is the minimum span over all L(2,1) labelings of G. We will show that when m>=6 and n>=3, lambda(Pm x Cn) = 7 if and only if n is not a multiple of 7 and also provide the conditions on m and n such that lambda(Cm x Cn) <= 7.
10.05.2017 16:15
Torsten Ueckerdt
Karlsruhe Institute of Technology
Theoretical computer science
The k-Strong Induced Arboricity of a Graph

Motivated by a connection to vertex-distinguishing colorings, we initiate the study of a new graph covering parameters: The k-strong induced arboricity. For a graph G and a positive integer k, a k-strong induced forest F in G is an induced forest in which every component has at least k edges. An edge in G is called k-valid if it is contained in at least one k-strong induced forest. The k-strong induced arboricity fk(G) is the smallest number m such that all k-valid edges of G can be covered with m k-strong induced forests in G.

We demonstrate that the k-strong induced arboricity is not monotone, neither in k, nor under taking subgraphs or even induced subgraphs. In particular we construct 2-degenerate graphs G with fk(G)
3 and fk+1(G) arbitrarily large. Focusing on the supremum fk(C) of fk(G) among all graphs G from a given graph class C, we prove that fk(G) is finite whenever C is of bounded expansion. For the class C of planar graphs we prove that fk(C) is 8,9 or 10. Moreover we give necessary and sufficient conditions for f1(C) to be finite in terms of r-shallow minors of graphs in C, a notion recently introduced by Nešetřil and Ossona de Mendez.

This is based on joint work with Maria Axenovich, Philip Dörr, Daniel Gonçalves, and Jonathan Rollin.

10.05.2017 12:15
Maciej Bendkowski
Computer science foundations
Analytic combinatorics: an introduction
In our talk we outline the main concepts and techniques of analytic combinatorics used to investigate properties of large random algebraic structures. We discuss the central interpretation of generating functions as functions analytic at the origin allowing to relate their analytic properties with the quantitative properties of studied structures. Finally, we briefly excerpt the techniques of singularity analysis allowing us to access the asymptotic form of corresponding counting sequences or investigate the probability distribution of interesting combinatorial parameters.
09.05.2017 14:15
Aleksandra Nowak
The Fully Homomorphic Encryption and Approximate Greatest Common Divisor Problem

We briefly introduce the definition of fully homomorphic encryption and describe the two main problems on which are based latest FHE schemes: The LWE/Ring-LWE and AGCD problems. We discuss their advantages and the relations between them. We present the definition of bootstrapping and investigate the FHE scheme based on the AGCD problem as published in [1].


[1] J. H. Cheon, D. Stehlé, Fully Homomorphic Encryption over the Integers Revisited, EUROCRYPT'10 Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques, pp. 24--43.

04.05.2017 16:15
Grzegorz Bukowiec
Combinatorial Optimization
Even factors of graphs
An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. It has been shown that if a graph G has an even factor, it also has an even factor F such that |E(F)| >= 4/7 (|E(G)| + 1). 4/7 is the best possible ratio here, but we will try to strengthen this lower bound by taking the set of vertices of degree 2 into consideration.
27.04.2017 16:15
Jakub Szarawski
Combinatorial Optimization
A greedy approach to the Turtle Tower problem
In the Turtle Tower problem we are given n turtles with a mass and capacity for each of them. We are looking for the highest tower possible, regarding that capacity of every turtle in the tower cannot be exeeded by the sum of the masses of turles it carry. Presented solution is faster than commonly known dynamic one.
26.04.2017 16:15
Marcin Pilipczuk
University of Warsaw
Theoretical computer science
Subexponential Parameterized Algorithms for Planar Graphs, Apex-Minor-Free Graphs and Graphs of Polynomial Growth via Low Treewidth Pattern Covering

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

1) A induces a subgraph of G of treewidth O(√k log k), and

2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log2k)nO(1))−1, where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log2k)nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Michał Pilipczuk, and Saket Saurabh: and

26.04.2017 12:15
Konrad Kalita
Computer science foundations
Java Generics are Turing Complete by Radu Grigore
This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by
Kennedy and Pierce in 2007. It also follows that Java’s type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser
generator for fluent interfaces.
25.04.2017 14:15
Michał Ziobro
Introduction to Homomorphic Encryption

The talk is divided into two parts. In the first part we briefly introduce Fully Homomorphic Encryption and a presentation of a classic example described in [1]. In the second part, we bring up a subject of partially homomorphic encrytpion schemes over finite fields, presented in [2].


[1] C. Gentry, Computing Arbitrary Functions of Encrypted Data, 2008 (pdf)
[2] J. Liu, L. Chen and S. Mesnager, Partially homomorphic encryption schemes over finite fields, 2016 (pdf)

20.04.2017 16:15
Helena Borak, Zygmunt Łenyk
Combinatorial Optimization
Necklaces, Convolutions, and X + Y, A new upper bound for the online square packing
Necklaces, Convolutions, and X + Y

The necklace alignment problem is to find the optimal rotation of the necklaces to best align the beads, when we have two necklaces given, each with n beads at arbitrary positions. Alignment is measured according to the ℓ_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = ∞ and how these problems can be reduced to convolution problems which can be solve in subquadratic time. Besides, we say how the necklace alignment problems, and their corresponding convolution problems, are also intrinsically connected to problems on X + Y matrices.

A new upper bound for the online square packing

In online square packing problem we try to minimise the height of squares on a plane with width 1. Squares come one by one, they can’t overlap and once set, it’s position can’t be changed. A new upper bound (ratio between algorithm result and optimal packing) is found by applying modified version of previously used First Fit Shelf algorithm.
19.04.2017 16:15
Lech Duraj, Adam Polak
Theoretical computer science
Longest Common Strictly Increasing Subsequecnce

The Longest Common Increasing Subsequence problem is a variant of classic Longest Common Subsequence problem, which can be solved in quadratic time with a simple dynamic programming algorithm. During the talk we will show a reduction from the Orthogonal Vectors problem to the Longest Common Increasing Subsequence problem which proves that the latter cannot be solved in strongly subquadratic time unless the SETH is false.


Simple modifications of the reduction prove that the problem for k sequences cannot be solved in O(nk-ε) time, that the same lower bounds apply to the Longest Common Weakly Increasing Subsequence, and that the assumption of SETH can be replaced with a weaker statement about satisfiability of non-deterministic branching programs.

12.04.2017 12:15
Jarek Duda
Computer science foundations
Boundaries for hashing problem, or how many bits ones individuality costs
I will talk about information-theoretic boundaries for the hashing problem, the Bloom filter, and generally about informational content of structures like trees and graphs. While the label size has to grow like logarithm of the population size, neglecting information about the order (lg(n!) bits), we get a linear growth of entropy of population, allowing to bound 'the cost of individuality' asymptotically to ~2.33275 bits per object.
06.04.2017 16:15
Andrzej Głuszyński, Jakub Nowak
Combinatorial Optimization
Local Antimagic Vertex Coloring of a Graph, A short proof of Cayley's tree formula
Local Antimagic Vertex Coloring of a Graph

The edge labelling is called 'local antimagic', if for all vertices sum of labels for incident edges is different for every two adjacent vertices. Such sum induce a correct vertex colouring. The local antimagic chromatic number - X_la(G) - is the minimum number of colours used by any proper local antimagic labelling. In the paper authors present results on this parameter for trees, friendship, wheel and clique graphs.

A short proof of Cayley's tree formula

Cayley’s tree formula is a very elegant result in Graph Theory. The problem is to find the number of all possible trees on a given set of labeled vertices. For n = 2 and vertex set {v1, v2}, we have only one tree. For n = 3 and vertex set {v1, v2, v3}, we have 3 different trees. Similarly for n = 4, we have 16 trees. We give a short proof of Cayley’s tree formula for counting the number of different labeled trees on n vertices.

Alok Bhushan Shukla, A short proof of Cayley's tree formula.
05.04.2017 12:15
Szymon Stankiewicz
Computer science foundations

A packing polynomial is a polynomial that maps the set N^2 of lattice points with nonnegative coordinates bijectively onto N. Cantor constructed two quadratic packing polynomials, and Fueter and Polya proved analytically that the Cantor polynomials are the only quadratic packing polynomials.
The purpose of this paper is to present a beautiful elementary proof of Vsemirnov of the Fueter-Polya theorem. It is a century-old conjecture that the Cantor polynomials are the only packing polynomials on N^2.

04.04.2017 14:15
Mateusz Jachna
Secure Hash Algorithms family and the recently found collision for SHA-1
28.03.2017 14:15
Piotr Wójcik
Quantum Authentication with Key Recycling

We show that a family of quantum authentication protocols introduced in FOCS 2002 can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all non-recycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource.


[1] Christopher Portmann, Quantum Authentication with Key Recycling (pdf)

23.03.2017 16:15
Aleksandra Mędrek, Marcin Muszalski
Combinatorial Optimization
Planning for Fast Connectivity Updates
Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d > 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
  1. Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007
21.03.2017 14:15
Jan Szczepaniec
Inclusive Block Chain Protocols

Distributed cryptographic protocols such as Bitcoin and Ethereum use the block chain to synchronize a global log of events between nodes in their network. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly.
Inclusive Block Chain Protocol is a alternative structure consists of a directed acyclic graph of blocks to the chain that allows for operation at much higher rates. It is showed that with this system the advantage of highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks.

[1] Lewenberg Y., Sompolinsky Y., Zohar A., Inclusive Block Chain Protocols. In: Böhme R., Okamoto T. (eds) Financial Cryptography and Data Security, 2015. Lecture Notes in Computer Science, vol 8975. Springer, Berlin, Heidelberg (pdf)

16.03.2017 16:15
Patryk Urbański
Combinatorial Optimization
Generating Linear Extensions Fast

One of the most important sets associated with a poset P is its set of linear extensions, E(P). In this paper, we present an algorithm to generate all of the linear extensions of a poset in constant amortized time; that is, in time O(e(P)), where e(P) = |E(P)|. The fastest previously known algorithm for generating the linear extensions of a poset runs in time O(n*e(P)), where n is the number of elements of the poset. Our algorithm is the first constant amortized time algorithm for generating a ``naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furthermore, we show that linear extensions can be generated in constant amortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to efficiently count linear extensions, and to compute P(x < y), for all pairs x,y, in time O(n^2 + e(P)).

Gara Pruesse, Frank Ruskey. Generating Linear Extensions Fast. SIAM J. Comput. Vol. 23, No. 2 (1994), pp. 373-386.

16.03.2017 14:15
Jakub Cisło, Grzegorz Jurdziński
Tight Hardness Results for LCS and other Sequence Similarity Measures
15.03.2017 16:15
Manuel Bodirsky
TU Dresden
Theoretical computer science
The tractability conjecture for finitely bounded homogeneous structures
Finitely bounded homogeneous structures form a large class of infinite structures that can be seen as a generalisation of the class of all finite structures. Many results about finite structures, in particular in the context of the complexity of constraint satisfaction problems, can be generalised to this larger class. In this talk I will present a reformulation of a tractability conjecture for CSPs for this class in terms of polymorphisms, due to Barto and Pinsker (LICS 2016), and I will present a proof that the condition given in the tractability conjecture is decidable (under some Ramsey-theoretic assumptions that might hold in general for all reducts of finitely bounded homogeneous structures).
15.03.2017 12:15
Łukasz Lachowski
Computer science foundations
Impossibility of Distributed Consensus with One Faulty Process by MICHAEL J. FISCHER, NANCY A. LYNCH AND MICHAEL S. PATERSO
The consensus problem involves a asynchronous system of processes, some of which may be unreliable.The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
14.03.2017 14:15
Marcin Briański
Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

The talk is based on the paper with the same title by Rosario Gennaro, Craig Gentry and Bryan Parno.

Verifiable Computation enables a computationally weak client to "outsource" the computation of a function F on various inputs x1, ..., xk to one or more workers. The workers return the result of the function evaluation, e.g., yi = F(xi), as well as a proof that the computation of F was carried out correctly on the given value xi. The verification of the proof should require substantially less computational effort than computing F(xi) from scratch.

We present a protocol that allows the worker to return a computationally sound, non-interactive proof that can be verified in O(m) time, where m is the bit-length of the output of F. The protocol requires a one-time pre-processing stage by the client which takes O(|C|) time, where C is the smallest Boolean circuit computing F. Our scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the values xi or yi.

09.03.2017 16:15
Grzegorz Matecki
Combinatorial Optimization
Boolean dimension of posets
A boolean dimension bdim(P) of a poset P=(X,<) is a smallest number k for which there is a set l1, l2, ..., lk of labelings X:->N and a boolean formula f(a1, ..., ak) such that the following is true: x < y in P iff f(a1, .., a_k) = 1 where ai =1 iff li(x) < li(x).
Generally, it is simple to observe that bdim(P) <= dim(P). Also, it is known that there is a constant c such that bdim(n) <= c log(n) for any poset P of size n.
The are few interesting open problems for boolean dimension:
1) Is boolean dimension of the boolean lattice of size n less that n?
2) Is there a constant c such that bdim(P) < c for any planar poset P?
09.03.2017 14:00
Sylwester Klocek, Wojciech Kruk
The Alternating Stock Size Problem and the Gasoline Puzzle
08.03.2017 12:15
Maciej Bendkowski
Computer science foundations
Boltzmann samplers: random generation of combinatorial structures with an application to lambda calculus
In their seminal paper, Duchon et al. proposed a surprisingly simple, general-purpose framework of Boltzmann samplers meant for random generation of combinatorial structures. In this talk we revisit their method and discuss its elegant relation with analytic combinatorics as well as important practical implementation details. Finally, we discuss the application of Boltzmann samplers to the random generation of lambda terms used, e.g. in testing functional programming compilers.
07.03.2017 14:15
Zygmunt Łenyk
Speeding up modular multiplication using Montgomery and Barrett reduction
In the talk we present Montgomery and Barrett reductions that are used to speed up modular computations. In both reductions some pre-computations are made allowing for replacing subsequent expensive divisions by some fixed modulus with much cheaper operations involving a suitable power of 2. This is particularly useful when many modular divisions by the same modulus are performed (for example in finite field arithmetic or in RSA).
07.03.2017 14:15
Mateusz Twaróg, Łukasz Majcher
Combinatorial Optimization
Combinatorial library core
Presentation and discussion on core functionalities of the c++ combinatorial library. introduction to classes representing graphs, graph traversing algorithm templates and simple GUI.