Seminars
28.03.2017 14:15 Piotr Wójcik 
Cryptology 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 nonrecycled 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. References: [1] Christopher Portmann, Quantum Authentication with Key Recycling (pdf) 
29.03.2017 12:15 Szymon Stankiewicz 
Computer science foundations CANTOR POLYNOMIALS AND THE FUETERPOLYA THEOREM by MELVYN NATHANSON 
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. 
04.04.2017 14:15 Mateusz Jachna 
Cryptology Secure Hash Algorithms family and the recently found collision for SHA1 
19.04.2017 16:15 Lech Duraj, Adam Polak 
Theoretical computer science Longest Common Strictly Increasing Subsequecnce 
26.04.2017 16:15 Marcin Pilipczuk University of Warsaw 
Theoretical computer science Subexponential Parameterized Algorithms for Planar Graphs, ApexMinorFree 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 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 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 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: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778. 
31.05.2017 16:15 Piotr Micek 
Theoretical computer science Ramsey Theory for Binary Trees and the Separation of Treechromatic Number from Pathchromatic Number 
We propose a Ramsey theory for binary trees and prove that for every
Joint work with Fidel BarreraCruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter. 
Poprzednie referaty
23.03.2017 16:15 Aleksandra Mędrek, Marcin Muszalski 
Combinatorial Optimization Planning for Fast Connectivity Updates 
21.03.2017 14:15 Jan Szczepaniec 
Cryptology 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.

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 #Pcomplete. 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)). 
16.03.2017 14:15 Jakub Cisło, Grzegorz Jurdziński 
Algorytmika 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 Ramseytheoretic 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 
Cryptology NonInteractive 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 x_{1}, ..., x_{k} to one or more workers. The workers return the result of the function evaluation, e.g., y_{i} = F(x_{i}), as well as a proof that the computation of F was carried out correctly on the given value x_{i}. The verification of the proof should require substantially less computational effort than computing F(x_{i}) from scratch. We present a protocol that allows the worker to return a computationally sound, noninteractive proof that can be verified in O(m) time, where m is the bitlength of the output of F. The protocol requires a onetime preprocessing 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 x_{i} or y_{i}. 
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 
Algorytmika 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, generalpurpose 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 
Cryptology 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 precomputations 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). 
01.03.2017 12:15 Michał Zwonek 
Computer science foundations Wielomianowe kodowania 
Rozważany będzie problem istnienia wielomianowej bijekcji, najniższego stopnia, między N^k, a N. Przedstawione będą także problemy otwarte związane z tą tematyką. Materiały do wystąpienia: 1) Elementarny dowód Twierdzenie FeuterPolya (jedyny kwadratowy i bijektywny wielomian N^2>N to funkcja cantore'a) https://arxiv.org/abs/1512. 2) Praca, w której autorzy pokazują nieistnienie wielomianów 3 i 4 stopnia. http://www.sciencedirect.com/ 3) Praca podobnie tematyczna odnosząca się do problemu istnienia wielomianów bijektywnych z pewnego sektora N^2 w N. (To o czym wspomniałem na koniec, opis tego problemu jest też pod koniec w 1) ). Pod koniec pracy jest opisane 6 problemów otwartych związanych z tą tematyką. https://arxiv.org/abs/1305. 4) W podobnej tematyce. http://www.sciencedirect.com/science/article/pii/0022314X78900355

28.02.2017 Michał Dyrek 
Cryptology LLL algorithm and its applications in Number Theory and Cryptography 
The talk is devoted to the algorithm by A. Lenstra, H. Lenstra and L. Lovász dated 1982 allowing for approximation of Shortest Vector Problem in polynomial time. We will present the idea of the algorithm and highlight its applications such as factoring polynomials over Q, constructing polynomials with small coefficients and connections with attacks on RSA. 
26.01.2017 16:15 Wojciech Kruk, Maciej Woźniak 
Combinatorial Optimization A few open problems 
We mentioned the following open problems in graph theory and discrepancy theory: 1. Erdos discrepancy problem 2. Hoang  Reed conjecture 3. Seagull problem  a consequence of Hadwiger's conjecture 
25.01.2017 16:15 01.03.2017 16:15 Grzegorz Guśpiel 
Theoretical computer science Partial Visibility Representation Extension Problem 
We study a class of graphs that have a special geometric representation. By a bar visibility representation of an undirected graph we mean a function that associates with each vertex of a graph a horizontal line segment in such a way, that between segments representing two ends of an edge there is a vertical strip (of visibility). In case of directed graphs, we additionally assume that the visibility is from the bottom to the top, that is the line segment representing the source of the edge is below the one for the target. Graphs admitting such representations are well understood and can be recognized in linear time, both in the undirected and in the directed case. We work in a more subtle setting, where line segments are already associated with some vertices of a graph, and the question is if this can be extended to a bar visibility representation of an entire graph. We prove some results on complexity of this kind of problems. This is joint work with Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk and Giuseppe Liotta. The manuscript is available here: https://arxiv.org/abs/1512.00174 
25.01.2017 12:00 Sylwester Klocek 
Computer science foundations Incompleteness, Undecidability and Automated Proofs by Cristian S. Calude and Declan Thompson 
Incompleteness and undecidability have been used for many years as arguments against automatising the practice of mathematics. The advent of powerful computers and proofassistants – programs that assist the development of formal proofs by humanmachine collaboration – has revived the interest in formal proofs and diminished considerably the value of these arguments. In this paper we discuss some challenges proofassistants face in handling undecidable problems – the very results cited above – using for illustrations the generic proofassistant Isabelle. 
24.01.2017 Kamil Sałaś 
Cryptology Lower Bounds for Discrete Logarithms 
In the talk we will present the computational complexity of the discrete logarithm in the context of "generic algorithms", that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as unique binary string. For discrete logarithm, any generic algorithm must perform Ω(p^1/2) group operations, where p is the largest prime dividing the order of the group. 
19.01.2017 Paweł Petecki Akademia GórniczoHutnicza 
Combinatorial Optimization Symmetry breaking polynomial 
Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetrybreaking if for every nonidentity automorphism φ in Γ, there is some vertex v of G such that c(v)≠c(φ(v)). There has been a lot of work on the minimum number of colors in a symmetrybreaking coloring of G. We discuss here a different problem: counting the number of kcolorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial ψ_{G}. For positive integer k (number of colors), ψ_{G}(k) is the number of kcolorings that break all nontrivial symmetries of the graph G. 
18.01.2017 16:15 Marian Mrozek 
Theoretical computer science The discrete charm of Morse theory 
The lecture will start with recalling P.S. Alexandroff's Theorem (1937) on mutual equivalence of posets and T_{0} topologies on finite sets. Next, we will outline the combinatorial version of the classical Morse Theory presented by R. Forman in 1998. Then, we will elaborate Forman's ideas towards the combinatorial topological dynamics with potential applications in Big Data problems and time series. The topics of the lecture will be expanded in a course for PhD students in the summer semester 2016/17. 
18.01.2017 12:00 Michał Ziobro 
Computer science foundations Inhabitation in SimplyTyped LambdaCalculus through a LambdaCalculus for Proof Search by Jose Espırito Santo, Ralph Matthes, Luıs Pinto 
Kontynuacja seminarium z 23.11.2016 
17.01.2017 Grzegorz Bukowiec 
Cryptology A quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic 
Until recently, all the algorithms for computing discrete logarithm had a subexponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasipolynomial complexity for discrete logarithm in finite fields of small characteristic and that even for other cases still surpasses the Function Field Sieve method. References: [1] R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf) 
11.01.2017 16:15 Patryk Mikos 
Theoretical computer science Online coloring of intervals with bandwidth 
We study the online interval coloring problem with bandwidth. The input is a sequence of pairs J_{i}= (I_{i},w_{i}) where I_{i} is an interval on the real line and w_{i} is a real number from (0,1]. In this setting a proper coloring is a function f:J_{i }→N such that for each color c and any point p on the real line, the sum of bandwidths of intervals containing p and colored by c does not exceed 1. The best known lower bound on the competitive ratio in this problem is 24/7. We present an explicit strategy for Presenter that increases the competitive ratio ifor this problem to at least 4.1626. 
11.01.2017 12:00 Patryk Mikos 
Computer science foundations ON THE NUMBER OF DISTINCT LANGUAGES ACCEPTED BY FINITE AUTOMATA WITH n STATES by Michael Domaratzki, Derek Kisman and Jeffrey Shallit 
We give asymptotic estimates and some explicit computations for both the number of distinct languages and the number of distinct finite languages over a kletter alphabet that are accepted by deterministic finite automata (resp. nondeterministic finite automata) with n states. 
10.01.2017 Szymon Policht 
Cryptology Faster operations on elliptic curves using Edwards curves 
Elliptic curve cryptography is a broad and commonly used section of modernday cryptography. Because of that, the speed of elliptic curve operations directly impacts the performance of many current systems. In this talk we'll show how to speed up those operations using Edwards curves. References: [1] Bernstein D.J., Lange T. (2007) Faster Addition and Doubling on Elliptic Curves. In: Kurosawa K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg (https://eprint.iacr.org/2007/286.pdf) 
05.01.2017 14:15 Jan Derbisz, Jakub Łabaj 
Algorytmika How to sort by walking on a tree 
We consider a tree with n vertices. On vertex number x there is a box with label p(x), with the function p being a permutation of {1,2,...,n}. A robot is walking on the tree, carrying at most one box at a time. If a box is placed where robot is standing, it can swap this box with the one being carried. The robot's goal is to sort the boxes, placing each one at the vertex with its number. The paper by D. Graf gives an algorithm computing the shortest possible robot's walk in quadratic time, as well as the proof that the problem becomes NPcomplete if planar graphs are considered instead of trees. 
04.01.2017 12:00 Konrad Kalita 
Computer science foundations ANALYTIC MODELS AND AMBIGUITY OF CONTEXTFREE LANGUAGES by Philippe Flajolet 
We establish that several classical contextfree languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour. To that purpose, we survey some general results on elementary analytic properties and enumerative uses of algebraic functions in relation to formal languages In particular, the paper contains a general density theorem for unambiguous contextfree languages. 
03.01.2017 
Cryptology (Cancelled) 
22.12.2016 16:15 Łukasz Majcher, Jan Szczepaniec 
Combinatorial Optimization Convex ppartitions of bipartite graphs 
A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time. 
21.12.2016 16:15 Maciej Bendkowski 
Theoretical computer science Boltzmann samplers: a framework for random generation of combinatorial structures with an application to lambda calculus 
In their seminal paper, Duchon et al. proposed a surprisingly simple, generalpurpose 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. 
20.12.2016 12:00 Bartłomiej Puget 
Cryptology An introduction to quantum computing and cryptography II 
15.12.2016 14:15 Michał Glapa, Franciszek Stokowacki 
Algorytmika Maximum matching with algebraic methods 
In 2006, a celebrated result by Mucha and Sankowski stated that the maximum matching problem can be done by Gaussian elimination. The complexity of this algorithm depends on matrix multiplication, but certainly beats O(n^{2.5}) longstanding record of MicaliVazirani algorithm. 
15.12.2016 Anna Kobak 
Combinatorial Optimization Open problems in graph theory concerning minors. 
We mentioned following open problems in graph theory:

14.12.2016 16:15 Grzegorz Matecki 
Theoretical computer science TwoDimensional Irregular Packing Problem 
We present results on packing irregular shapes onto given sheets of material. 
14.12.2016 12:00 Piotr Wójcik 
Computer science foundations Enumeration and random generation of accessible automata by Frederique Bassino and Cyril Nicaud 
We present a bijection between the A_n of deterministic and accessible automata with n states on a kletters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn + 1 elements into n nonempty subsets. This combinatorial construction shows that the asymptotic order of the cardinality of A_n is related to the Stirling number. Our bijective approach also yields an efficient random sampler, for the uniform distribution, of automata with n states, its complexity is O(n^3/2), using the framework of Boltzmann samplers. 
13.12.2016 12:00 Krzysztof Kleiner 
Cryptology An introduction to quantum computing and cryptography I 
In this talk we're going to discuss quantum informatics and its impact on the field of cryptography. We will introduce the basic concepts of quantum computing as well as cryptography based on Quantum Key Distribution scheme, one of the aspects of quantum informatics which already is being used in practice. Then we will present Shor's algorithm for polynomialtime factorization, responsible for the cryptosystems based on the hardness of factorization or discrete logarithm (in abelian groups) being no longer secure against an adversary with access to a quantum computer.

08.12.2016 Lech Duraj 
Algorytmika A short tale of matrix multiplication 
In recent years, some new algorithms for matrix multiplication problem were presented. Each of them is, however, only slightly faster than previous ones, while requiring substantially more complex analysis. Because of this, the longstanding question of optimal matrix multiplication algorithm seems even harder. In my presentation, a short survery of the matrix multiplication algorithm is given. The presentation is based on François Le Gall's survey lecture of 2014. 
08.12.2016 Zygmunt Łenyk 
Combinatorial Optimization Rendezvous on the line. 
This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. In line case, players are placed on the line with distance 2, without knowing neither on which side is their partner, nor the direction of the line. I'll concentrate on the symmetric case where players must follow a specific (but maybe mixed) strategy. The conjecture is that best expected time of meeting two players equals 4.25. 
07.12.2016 12:00 Jakub Brzeski 
Computer science foundations ENUMERATION OF FORMAL LANGUAGES by Michael Domaratzki 
We survey recent results on the enumeration of formal languages. In particular, we consider enumeration of regular languages accepted by deterministic and nondeterministic finite automata with n states, regular languages generated by regular expressions of a fixed length, and !regular languages accepted by Müller automata. We also survey the uncomputability of enumeration of contextfree languages and more general structures. 
06.12.2016 Marek Rusinowski 
Cryptology Security of instant messaging applications. 
Nowadays billions of people around the world are sharing sensitive information using instant messaging applications. We will look into the current state of IM security, the problems in this area and a few encryption protocolsOTR and Signal Protocol in particularthat provide security features desired by users. 
01.12.2016 Aleksandra Mędrek, Krzysztof Maziarz 
Algorytmika Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back 
The paper by Aleksander Mądry describes a new approach to the maximum flow problem. We define an electrical flow by assigning resistances to every edge and minimizing total energy instead of maximizing flow. Any flow network can be reduced to some electrical flow problem, using auxiliary reductions to some bipartite matching problems. The main result is a new maximum flow algorithm, working in O(m10/7). The presentation will cover a simpler, O(m3/2) version of the algorithm. 
01.12.2016 Patryk Urbański 
Combinatorial Optimization Coloring Ordinary Maps, Maps of Empires and Maps of the Moon 
A short review of generalized map coloring problems:

01.12.2016 Mateusz Twaróg 
Combinatorial Optimization Second Neighborhood via First Neighborhood in Digraphs 
30.11.2016 18:15 Bartosz Walczak 
Theoretical computer science Coloring curves that cross a fixed curve 
A class of graphs is χbounded if the chromatic number of all graphs in the class is bounded by some function of their clique number. String graphs are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are χbounded. In particular, it is known since 2012 that the class of all string graphs is not χbounded. We prove that for every integer t≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χbounded. This result is best possible in several aspects; for example, the upper bound t on the number of crossings with the fixed curve cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in socalled kquasiplanar topological graphs. This is joint work with Alexandre Rok. 
30.11.2016 12:00 Yauheni Ananchuk 
Computer science foundations ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS by ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI 
Binary Constraint Problems have traditionally been considered as Network Satisfaction Problems over some relation algebra. A constraint network is satisfable if its nodes can be mapped into some representation of the relation algebra in such a way that the constraints are preserved. A qualitative representation is like an ordinary representation, but instead of requiring (a ; b) = a j b , as we do for ordinary representations, we only require that. A constraint network is qualitatively satisfable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfable then it is clearly qualitatively satisfable, but the converse can fail. However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfable if and only if it is qualitatively satisfable. Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over nonassociative algebras. We prove that computationally, qualitative representations have many advantages over ordinary representations: whereas many finite relation algebras have only infnite representations, every finite qualitatively representable algebra has a finite qualitative representation; the representability problem for (the atom structures of) finite nonassociative algebras is NPcomplete; the network satisfaction problem over a finite qualitatively representable algebra is always ; the validity of equations over qualitative representations is coNPcomplete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebra 
29.11.2016 Anna Kobak 
Cryptology Breaking RSA vs Factoring in generic ring model 
In the talk we present results of Aggarwal and Maurer [1], who showed that a generic ring algorithm for breaking RSA with modulus $N$ can be converted into an algorithm for factoring $N$. The results imply that any attempt at breaking RSA without factoring $N$ will be nongeneric and hence will have to manipulate the particular bitrepresentation of the input modulo $N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.
References: [1] D. Aggarwal, U. Maurer, Breaking RSA Generically is Equivalent to Factoring, EUROCRYPT 2009 
24.11.2016 Wojciech Łopata 
Combinatorial Optimization Several open problems from game theory, graph theory and combinatorics. 
I'll briefly introduce the audience to two unrelated areas: book embedding and mechanism design, and walk through some open problems in those areas. 
24.11.2016 Dominika Salawa, Jakub Cisło 
Algorytmika Greedy algorithms for Steiner forest 
The paper, resolves a longstanding open question: is the greedy approach for Steiner forest problem optimal up to multiplicative constant? The result by Anupam Gupta and Amit Kumar proves that in fact it is, with constant being at most 96. While some approximation algorithms for this problem, using linear programming, were previously known, this is the first known bound for a greedy algorithm. 
23.11.2016 Piotr Danilewski 
Theoretical computer science Functional Code Building 

23.11.2016 Michał Ziobro 
Computer science foundations Inhabitation in SimplyTyped LambdaCalculus through a LambdaCalculus for Proof Search by Jos´e Espırito Santo, Ralph Matthes, Luıs Pinto 
A new, comprehensive approach to inhabitation problems in simplytyped lambdacalculus is shown, dealing with both decision and counting problems. This approach works by exploiting a representation of the search space generated by a given inhabitation problem, which is in terms of a lambdacalculus for proof search that the authors developed recently. The representation may be seen as extending the CurryHoward representation of proofs by lambdaterms, staying within the methods of lambdacalculus and type systems. Our methodology reveals inductive descriptions of the decision problems, driven by the syntax of the proofsearch expressions, and the end products are simple, recursive decision procedures and counting functions. 
22.11.2016 Aleksandra Nowak 
Cryptology Lattice Cryptography and The Learning With Errors Problem 
17.11.2016 Paweł Kubiak 
Combinatorial Optimization Succinct Data Structures 
17.11.2016 Patryk Gołębiowski, Wojciech Kruk 
Algorytmika Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms 
In the last decade, there has been a substantial amount of research in finding routing algorithms designed specifically to run on realworld graphs. The paper by Colin White analyzes some of these algorithms and gives lower bounds for their complexity. 
16.11.2016 Bartłomiej Bosek 
Theoretical computer science Every digraph is majority 4choosable 
A majority coloring of a digraph is a coloring of its vertices such that for each vertex at most half of its outneighbors has the same color as that vertex. A digraph D is majority kchoosable if for any assignment of color lists of size k to the vertices there is a majority coloring of D from these lists. We prove the statement in the title. This gives a positive answer to a question posed recently in 1. This is a joint work with Marcin Anholcer and Jarosław Grytczuk. 
16.11.2016 Michał Zieliński 
Computer science foundations Most programs stop quickly or never halt by Cristian S. Calude and Michael A. Stay 
The aim of this paper is to provide a probabilistic, but nonquantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random Nbit program has halted by a random time.We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k >0, we can effectively compute a time bound T such that the probability that an Nbit program will eventually halt given that it has not halted by T is smaller than 2^{−k}. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that “long” runtimes are effectively rare. More formally, the set of times at which an Nbit program can stop after the time 2^{N+constant} has effectively zero density. 
15.11.2016 Piotr Kawałek 
Cryptology Teoretyczne podstawy kryptoanalizy 
Celem referatu jest przedstawienie teoretycznych modeli ataków kryptoanalitycznych oraz tematów pokrewnych wraz z przykładami. 
10.11.2016 Magdalena Gargas, Mateusz Jachna 
Algorytmika Max flows in O(nm) time, or better 
A new maxflow algorithm with O(nm + m16/15 log2 n) time complexity is presented. By combining this with previous results, an O(nm) algorithm may be obtained, resolving a longstanding open question. This work is due to James B. Orlin. 
10.11.2016 Grzegorz Bukowiec 
Combinatorial Optimization On more variants of the Majority Problem 
09.11.2016 26.10.2016 Adam Polak 
Theoretical computer science Open problems in online and approximation algorithms 
During the talk I will present several promising open problems including:

09.11.2016 Wojciech Kruk 
Computer science foundations On the generic undecidability of the Halting Problem for normalized Turing machines by Alexander Rybalov 
Hamkins and Miasnikov presented in 2004 a generic algorithm deciding the classical Halting Problem for Turing machines with oneway tape on a set of asymptotic probability one (on a socalled generic set). Rybalov in 2007 showed that there is no generic algorithm deciding this problem on strongly generic sets of inputs (some subclass of generic sets). In this paper we prove that there is no generic algorithm deciding the Halting Problem for normalized Turing machines on generic sets of inputs. Normalized Turing machines have programs with the following natural restriction: internal states with large indices are not allowed at the beginning of the program. This condition does not reduce the class of computable functions because for every Turing machine there exists a normalized Turing machine which computes the same function. Our proof holds for machines with oneway and twoway tape. It also implies that the HamkinsMiasnikov algorithm is not generic for normalized Turing machines. 
08.11.2016 Patryk Gołębiowski 
Cryptology Advanced Encryption Standard 
Advanced Encryption Standard (AES) is one of the most popular and widely adopted symmetric encryption scheme. In the talk we discuss how it works and why it is considered safe by the U.S. National Institute of Standards and Technology to use it for protecting classified information. 
03.11.2016 Gabriel Jakóbczak 
Combinatorial Optimization Proper orientations of some types of graphs 
Let G be a simple graph. We say that orientation of graph G is proper if for every pair of adjacent veritces u and v their indegrees are different. It was proved by Mieczysław Borowiecki, Jarosław Grytczuk and Monika Pilśniak that for every simple graph exists its proper orientation. Now we can define the proper orientation number of graph G as the minimum of the maximum indegree, taken over all proper orientations of G. We show that for some classes of bipartite graphs their proper orientation number is less than or equal to 6. We also show that this parameter is at most 4 for graphs which are trees and proof of that fact leads to a polynomialtime algorithm of finding proper orientation of such graphs.
Fiachra Knox, Sebastián González Hermosillo de la Maza, Bojan Mohar, and Cláudia Linhares Sales. Proper Orientations of Planar Bipartite Graphs. pages 26, sep 2016. 
03.11.2016 Krzysztof Francuz, Szymon Łukasz 
Algorytmika Fast and simple connectivity in graph timelines 
The presented paper (by J. Łącki and A. Karczmarz) deals with graph timelines  graphs with edges being created and destroyed over time. There is an effective algorithm for answering queries about reachability (finding a path between two given vertices) and biconnectivity (two disjoint paths) over some given time intervals. 
27.10.2016 Dawid Pyczek, Jakub Rówiński 
Algorytmika Faster deterministic sorting and priority queues in linear space 
The O(n log n) lower bound for sorting is valid only if the sorted objects allow no operations except comparing. For sorting integers, the bound can be broken  Mikkel Thorup's result of 1997 shows an O (n (log log n)^{2}) algorithm for sorting arbitrary integers. 
27.10.2016 Magdalena Gargas 
Combinatorial Optimization The geometry of nesting problems: A tutorial 
26.10.2016 Wojciech Łopata 
Computer science foundations Universality and Almost Decidability by Cristian S. Calude and Damien Desfontaines 
We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result—namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable—solves an open problem in [9]. We conclude with some open problems. 
25.10.2016 Marcin Briański 
Cryptology Unifying Zeroknowledge Proofs of Knowledge 
We present a simple zeroknowledge proof of knowledge protocol of which many protocols in the literature are instantiations. These include Schnorr's protocol for proving knowledge of a discrete logarithm, the FiatShamir and GuillouQuisquater protocols for proving knowledge of a modular root, protocols for proving knowledge of representations (like Okamoto's protocol), protocols for proving equality of secret values, a protocol for proving the correctness of a DiffieHellman key, protocols for proving the multiplicative relation of three commitments (as required in secure multiparty computation), and protocols used in credential systems. This shows that a single simple treatment (and proof), at a high level of abstraction, can replace the individual previous treatments. Moreover, one can devise new instantiations of the protocol. [1] Ueli Maurer, Unifying Zeroknowledge Proofs of Knowledge, Progress in Cryptology – AFRICACRYPT 2009, Vol. 5580 LNCS, pp 272286

20.10.2016 Helena Borak 
Combinatorial Optimization Exact algorithms for the twodimensional strip packing problem with and without rotations 
We propose exact algorithms for the twodimensional strip packing problem (2SP) with and without 90 degree rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branchandbound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations. 
20.10.2016 Mateusz Twaróg, Patryk Urbański 
Algorytmika Disjoint Set Union with randomized linking 
The most popular version of FindUnion algorithm uses path compression and linking by rank. The presented work of Goel, Khanna, Larkin and Tarjan gives an analysis of the same algorithm, but with arbitrary (randomized) linking. 
19.10.2016 Bartosz Walczak 
Theoretical computer science Common tangents of two disjoint polygons in linear time and constant workspace 
A tangent of a polygon is a line touching but not crossing the polygon. Two disjoint polygons can have four, two, or no common tangents, depending on whether the convex hulls of the polygons are disjoint, overlapping, or nested. We describe a very simple lineartime constantworkspace algorithm to compute all common tangents of two disjoint polygons, each given by a readonly array of its corners in a cyclic order. This is joint work with Mikkel Abrahamsen. 
19.10.2016 Pola Kyzioł 
Computer science foundations The domino problem for selfsimilar structures by Sebastian Barbieri and Mathieu Sablik 
We defne the domino problem for tilings over selfsimilar structures of $Z^d$ given by forbidden patterns. In this setting we exhibit nontrivial families of subsets with decidable and undecidable domino problem. 
18.10.2016 Grzegorz Jurdzinski 
Cryptology Timing attacks 
Cryptosystems like AES or RSA use algorithms which runtime depends on input data or using CPU cache. Basing on this fact an attacker can find secret keys by choosing inputs and carefully measuring time needed for computations. In this talk I will present such attacks and how to prevent them.

13.10.2016 Krzysztof Barański 
Combinatorial Optimization LevelOriented TwoDimensional Packing Algorithms 
The paper includes an overview of several algorithms, their complexities and approximation ratios solving twodimensional strip packing problem: 1) FirstFit Decreasing Height (FFDH)  time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof] 2) NextFit Decreasing Height (NFDH)  time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof] 3) BestFit Decreasing Height (BFDH), BottomLeft (BL), Steinberg's algorithm, SplitFit (SF) 
13.10.2016 G. Bukowiec, S.Klocek 
Algorytmika FKT algorithm 
Counting all matchings in a given graph is a #Pcomplete problem. However, for planar graphs it can be done in polynomial time. The FKT algorithm does it by exploiting the connection between the notions of matrix determinant and matrix permanent. 
12.10.2016 Adam Polak 
Theoretical computer science Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequecnce? 
 Home
 Algorithmics Research Group
 Foundations of Computer Science
 Faculty of Mathematics and Computer Science
 Contact
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Photos
 People
 Maciej Bendkowski
 Szymon Borak
 Bartłomiej Bosek
 Iwona Cieślik
 Piotr Danilewski
 Lech Duraj
 Adam Gągol
 Monika Gillert
 Katarzyna Grygiel
 Jarosław Grytczuk
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Leszek Horwath
 Pawel M. Idziak
 Tomasz Kisielewski
 Karol Kosiński
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Łukasz Lachowski
 Wojciech Lubawski
 Agnieszka Łupińska
 Grzegorz Matecki
 Piotr Micek
 Patryk Mikos
 Andrzej Pezarski
 Adam Polak
 Michał Staromiejski
 Piotr Szafruga
 Maciej Ślusarek
 Bartosz Walczak
 Piotr Wójcik
 Michał Wrona
 Marek Zaionc
 Michał Zmarz
 Former colleagues