# Seminaria

 29.03.2017 16:15 TBA Informatyka Teoretyczna TBA
 25.01.2017 16:15 01.03.2017 16:15 Grzegorz Guśpiel Informatyka Teoretyczna 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

# Poprzednie referaty

 25.01.2017 12:00 Sylwester Klocek Podstawy Informatyki 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 proof-assistants – programs that assist the development of formal proofs by human-machine collaboration – has revived the interest in formal proofs and diminished considerably the value of these arguments. In this paper we discuss some challenges proof-assistants face in handling undecidable problems – the very results cited above – using for illustrations the generic proof-assistant Isabelle.
 24.01.2017 Kamil Sałaś Kryptologia 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órniczo-Hutnicza Optymalizacja Kombinatoryczna Symmetry breaking polynomial Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetry-breaking if for every non-identity 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 symmetry-breaking coloring of G. We discuss here a different problem: counting the number of k-colorings 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 k-colorings that break all non-trivial symmetries of the graph G.
 18.01.2017 16:15 Marian Mrozek Informatyka Teoretyczna The discrete charm of Morse theory The lecture will start with recalling P.S. Alexandroff's Theorem (1937) on mutual equivalence of posets and T0 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 Podstawy Informatyki Inhabitation in Simply-Typed Lambda-Calculus through a Lambda-Calculus for Proof Search by Jose Espırito Santo, Ralph Matthes, Luıs Pinto Kontynuacja seminarium z 23.11.2016
 17.01.2017 Grzegorz Bukowiec Kryptologia A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic Until recently, all the algorithms for computing discrete logarithm had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasi-polynomial 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 quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf)
 11.01.2017 16:15 Patryk Mikos Informatyka Teoretyczna Online coloring of intervals with bandwidth We study the online interval coloring problem with bandwidth. The input is a sequence of pairs Ji= (Ii,wi) where Ii is an interval on the real line and wi is a real number from (0,1]. In this setting a proper coloring is a function f:Ji →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 Podstawy Informatyki 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 k-letter alphabet that are accepted by deterministic finite automata (resp. nondeterministic finite automata) with n states.
 10.01.2017 Szymon Policht Kryptologia Faster operations on elliptic curves using Edwards curves Elliptic curve cryptography is a broad and commonly used section of modern-day 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 Sortowanie przez spacer po drzewie Rozważamy następujący problem: wierzchołki drzewa ponumerowane są kolejnymi liczbami naturalnymi, a dodatkowo w wierzchołku x leży skrzynka o numerze p(x), przy czym funkcja p jest permutacją zbioru {1,2,..,n}. Rozważamy chodzącego po drzewie robota, który może w danym momencie trzymać tylko jedną skrzynkę, może też podnieść napotkaną skrzynkę upuszczając aktualnie trzymaną. Celem robota jest posortować skrzynki (przenosząc każdą do wierzchołka o odpowiednim numerze), przechodząc po drzewie najkrótszą możliwą ścieżką. Praca D. Grafa podaje algorytm znajdujący taką ścieżkę w czasie O(n2) oraz dowód, że jeśli drzewo zastąpimy grafem planarnym, problem staje się NP-zupełny.
 04.01.2017 12:00 Konrad Kalita Podstawy Informatyki ANALYTIC MODELS AND AMBIGUITY OF CONTEXT-FREE LANGUAGES by Philippe Flajolet We establish that several classical context-free 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 context-free languages.
 03.01.2017 Kryptologia (Cancelled)
 22.12.2016 16:15 Łukasz Majcher, Jan Szczepaniec Optymalizacja Kombinatoryczna Convex p-partitions 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 Informatyka Teoretyczna 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, 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.
 20.12.2016 12:00 Bartłomiej Puget Kryptologia An introduction to quantum computing and cryptography II
 15.12.2016 14:15 Michał Glapa, Franciszek Stokowacki Algorytmika Skojarzenia w grafach metodami algebraicznymi Na seminarium omówiony zostanie przełomowa praca z 2006, autorstwa Muchy i Sankowskiego, opisująca algorytm obliczania skojarzeń w grafach za pomocą eliminacji Gaussa. Przedstawiony algorytm ma złożoność zależną od mnożenia macierzy, niższą niż O(n2.5), algorytmu Micaliego-Vaziraniego, który bardzo długo był najlepszą znaną metodą.
 15.12.2016 Anna Kobak Optymalizacja Kombinatoryczna Open problems in graph theory concerning minors. We mentioned following open problems in graph theory: Hadwiger's Conjecture Seagull Conjecture Jorgensen's Conjecture Unfriendly partitions and a few more conjectures concerning minors.
 14.12.2016 16:15 Grzegorz Matecki Informatyka Teoretyczna Two-Dimensional Irregular Packing Problem We present results on packing irregular shapes onto given sheets of material.
 14.12.2016 12:00 Piotr Wójcik Podstawy Informatyki 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 k-letters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn + 1 elements into n non-empty 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 Kryptologia 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 polynomial-time 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. References: [1] M. Hirvensalo, Quantum Computing (http://link.springer.com/book/10.1007/978-3-662-09636-9) [2] F. Benatti, M. Fannes, R. Floreanini, D. Petritis, Quantum Information, Computation and Cryptography (http://link.springer.com/book/10.1007/978-3-642-11914-9) [3] D. Deutsc, Lectures on Quantum Computation (http://www.daviddeutsch.org.uk/videos/) [4] U. Vazirani, BerkeleyX's Lectures: Quantum Mechanics and Quantum Computation (https://www.edx.org/course/quantum-mechanics-quantum-computation-uc-berkeleyx-cs-191x)
 08.12.2016 Lech Duraj Algorytmika Krótka opowieść o mnożeniu macierzy W ostatnich latach pojawiają się kolejne, coraz lepsze algorytmy mnożenia macierzy. Każdy z nich jest jednak tylko nieznacznie szybszy od poprzednich, będąc przy tym nierównie trudniejszy w zrozumieniu i analizie. Fakt ten jeszcze bardziej komplikuje otwarte od wielu lat pytanie o złożoność optymalnego algorytmu mnożenia macierzy. Celem prezentacji jest krótkie omówienie technik używanych do ataków na ten niezwykle ważny i trudny problem. Prezentacja oparta jest na przeglądowym wykładzie François Le Galla (autora ostatnich wyników w tym temacie) z 2014 roku.
 08.12.2016 Zygmunt Łenyk Optymalizacja Kombinatoryczna 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 Podstawy Informatyki 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 context-free languages and more general structures.
 06.12.2016 Marek Rusinowski Kryptologia 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 protocols---OTR and Signal Protocol in particular---that 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 Praca Aleksandra Mądrego opisuje nowe podejście do problemu maksymalnego przepływu, z użyciem tzw. przepływów elektrycznych. W tej technice krawędziom przypisywany jest opór, a zadaniem jest zminimalizowanie wydzielonej energii. Dowolną sieć przepływową można zredukować do zadania przepływu elektrycznego, z użyciem pośredniej redukcji poprzez warianty problemu skojarzenia w grafie dwudzielnym. Głównym rezultatem pracy jest algorytm przepływu o złożoności O(m10/7), na seminarium będzie prezentowana prostsza wersja algorytmu, działająca w O(m3/2).
 01.12.2016 Patryk Urbański Optymalizacja Kombinatoryczna Coloring Ordinary Maps, Maps of Empires and Maps of the Moon A short review of generalized map coloring problems: Heawood's empire coloring problem in the plane - 6M colors are sufficient to color a map of empires each consisting of at most M connected regions. Earth-Moon map coloring Mathematics Magazine Vol. 66, No. 4 (Oct., 1993), pp. 211-226problem - it is known that the chromatic number of thickness-2 graphs is between 9 and 12. It is an open problem to find the exact value. Coloring Ordinary Maps, Maps of Emipres, and Maps of the Moon. Joan P. Hutchinson. Mathematics Magazine. Vol. 66, No. 4 (Oct., 1993), pp. 211-226.
 01.12.2016 Mateusz Twaróg Optymalizacja Kombinatoryczna Second Neighborhood via First Neighborhood in Digraphs Second Neighborhood via First Neighborhood in Digraphs. Guantao Chen, Jian Shen, Raphael Yuster. Annals of Combinatorics. June 2003, Volume 7, Issue 1, pp 15–20.
 30.11.2016 18:15 Bartosz Walczak Informatyka Teoretyczna 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 so-called k-quasi-planar topological graphs. This is joint work with Alexandre Rok.
 30.11.2016 12:00 Yauheni Ananchuk Podstawy Informatyki 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 non-associative 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 non-associative algebras is NP-complete; the network satisfaction problem over a finite qualitatively representable algebra is always ; the validity of equations over qualitative representations is co-NP-complete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebra
 29.11.2016 Anna Kobak Kryptologia 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 non-generic and hence will have to manipulate the particular bit-representation 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 Optymalizacja Kombinatoryczna 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. Wikipedia: Book embedding Wikipedia: Mechanism design
 24.11.2016 Dominika Salawa, Jakub Cisło Algorytmika Greedy algorithms for Steiner forest Referowana praca rozstrzyga długo otwarty problem: czy budowanie drzewa Steinera zachłannym algorytmem daje wynik gorszy od optymalnego o stałą multiplikatywną? Autorzy (A. Gupta, A. Kumar) dowodzą, że tak, dla stałej równej 96. Jest to pierwsze znane oszacowanie wyniku algorytmu zachłannego, wcześniej podawane algorytmy aproksymacyjne dla tego problemu oparte były o programowanie liniowe.
 23.11.2016 Piotr Danilewski Informatyka Teoretyczna Functional Code Building A typical language translator uses a parser to convert an input string into some internal representation, usually in a form of an AST. The AST is then analyzed and transformed in passes. In the final pass, the AST is converted into the output, be it a machine code or source code of another language.   However, if we try to combine different languages, e.g. for a purpose of a multi-domain project, we may have a problem: each language uses different kinds of AST nodes, has different assumptions on the AST structure and features different pass algorithms. Settling for the common ground by limiting the node types, assumptions, and algorithms limits how the languages may reason about their code. Any high-level information is lost in such representation and high-level transformations cannot be defined.   Working on the common AST is similar to unstructured programming: AST acts as a global machine state. Any change to the state, e.g. introduced by a new language, may inadvertely affect the behavior of the existing languages. In regular programming we have moved away from unstructured programming towards higher abstraction levels, e.g. through functional programming. If it can be done to regular programming, can it be done to AST and code builders as well?   Our solution treats AST nodes not as objects of a fixed type. Instead, it is a function with its body describing entirely the behavior of such node. Even the connection between the nodes is represented internally by the function, in a form of continuations.  The passes over the AST are replaced by a single invocation of these functions. The node functions may contain code for multiple stages of code analysis. In order to reduce the run time these additional stages are scheduled through dynamic staging.   This gives the power of abstraction to code building. Even nodes come from different languages may interact, as long as they understand the passed arguments.   This major change on how a code is represented requires changes in how we think about common basic operations during language interpretation: - how do we link two nodes/functions together? - how do we create control flow structures? - how do we perform name lookups, even across different languages? - how do we optimize the code so that the AST layer dissapears when generating code? - what language-specific optimizations can be performed and how do we specify them?   We will address these questions in the upcoming talk.
 23.11.2016 Michał Ziobro Podstawy Informatyki Inhabitation in Simply-Typed Lambda-Calculus through a Lambda-Calculus for Proof Search by Jos´e Espırito Santo, Ralph Matthes, Luıs Pinto A new, comprehensive approach to inhabitation problems in simply-typed lambda-calculus 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 lambda-calculus for proof search that the authors developed recently. The representation may be seen as extending the Curry-Howard representation of proofs by lambda-terms, staying within the methods of lambda-calculus and type systems. Our methodology reveals inductive descriptions of the decision problems, driven by the syntax of the proof-search expressions, and the end products are simple, recursive decision procedures and counting functions.
 22.11.2016 Aleksandra Nowak Kryptologia Lattice Cryptography and The Learning With Errors Problem
 17.11.2016 Paweł Kubiak Optymalizacja Kombinatoryczna Succinct Data Structures
 17.11.2016 Patryk Gołębiowski, Wojciech Kruk Algorytmika Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms Tematem referatu jest praca Colina White'a dotycząca algorytmów poszukiwania ścieżki na grafach o szczególnym własnościach, mających w założeniu modelować rzeczywiste sieci dróg. Autor analizuje najpopularniejsze istniejące algorytmy i podaje dolne ograniczenia na ich złożoność.
 16.11.2016 Bartłomiej Bosek Informatyka Teoretyczna Every digraph is majority 4-choosable A majority coloring of a digraph is a coloring of its vertices such that for each vertex at most half of its out-neighbors has the same color as that vertex. A digraph D is majority k-choosable 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. S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colourings of Digraphs, Arxiv. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk Every digraph is majority 4-choosable, Arixv.
 16.11.2016 Michał Zieliński Podstawy Informatyki 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 non-quantum, 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 N-bit 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 N-bit 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 N-bit program can stop after the time 2^{N+constant} has effectively zero density.
 15.11.2016 Piotr Kawałek Kryptologia 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 W pracy opisany jest nowy algorytm przepływu działający w czasie O(nm + m16/15 log2 n). Istotny jest fakt, że przez połączenie go z poprzednio znanymi algorytmami daje to pozytywną odpowiedź na pytanie, czy da się obliczyć maksymalny przepływ w czasie O(nm). Autorem pracy jest James B. Orlin.
 10.11.2016 Grzegorz Bukowiec Optymalizacja Kombinatoryczna On more variants of the Majority Problem
 09.11.2016 26.10.2016 Adam Polak Informatyka Teoretyczna Open problems in on-line and approximation algorithms During the talk I will present several promising open problems including: Online Deadline Scheduling with Machine Augmentation Scheduling with Precedence Constraints Multiway Cut Traveling Repairman Problem
 09.11.2016 Wojciech Kruk Podstawy Informatyki 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 one-way tape on a set of asymptotic probability one (on a so-called 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 one-way and two-way tape. It also implies that the Hamkins-Miasnikov algorithm is not generic for normalized Turing machines.
 08.11.2016 Patryk Gołębiowski Kryptologia 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 Optymalizacja Kombinatoryczna 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 polynomial-time 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 2-6, sep 2016.
 03.11.2016 Krzysztof Francuz, Szymon Łukasz Algorytmika Fast and simple connectivity in graph timelines Referowana praca (autorstwa J. Łąckiego i A. Karczmarza) rozważa grafy, w którym krawędzie podlegają zmianom - są dodawane bądź usuwane. Opisany jest efektywny algorytm odpowiadający na pytania o osiągalność (istnienie ścieżki między dwoma wierzchołkami) i dwuspójność (istnienie dwóch rozłącznych ścieżek) na zadanych przedziałach czasowych.
 27.10.2016 Dawid Pyczek, Jakub Rówiński Algorytmika Faster deterministic sorting and priority queues in linear space Dolne ograniczenie O(n log n) na problem sortowania obowiązuje tylko, jeśli na sortowanych obiektach nie można wykonać żadnych operacji innych niż porównanie. Jeżeli natomiast sortujemy liczby całkowite, możliwe są szybsze algorytmy - referowana praca Mikkela Thorupa z 1997 opisuje algorytm działający w O (n (log log n)2).
 27.10.2016 Magdalena Gargas Optymalizacja Kombinatoryczna The geometry of nesting problems: A tutorial
 26.10.2016 Wojciech Łopata Podstawy Informatyki 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 Kryptologia Unifying Zero-knowledge Proofs of Knowledge We present a simple zero-knowledge 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 Fiat-Shamir and Guillou-Quisquater 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 Diffie-Hellman key, protocols for proving the multiplicative relation of three commitments (as required in secure multi-party 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 Zero-knowledge Proofs of Knowledge, Progress in Cryptology – AFRICACRYPT 2009, Vol. 5580 LNCS, pp 272-286
 20.10.2016 Helena Borak Optymalizacja Kombinatoryczna Exact algorithms for the two-dimensional strip packing problem with and without rotations We propose exact algorithms for the two-dimensional 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 branch-and-bound 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 Algorytm Find-Union w najbardziej znanej wersji implementowany jest przez las zbiorów rozłącznych z kompresją ścieżek i łączeniem według rang. Prezentowana praca, autorstwa Goela, Khanny, Larkina i Tarjana, analizuje złożoność w wersji z arbitralnym (losowym) łączeniem drzew.
 19.10.2016 Bartosz Walczak Informatyka Teoretyczna 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 linear-time constant-workspace algorithm to compute all common tangents of two disjoint polygons, each given by a read-only array of its corners in a cyclic order. This is joint work with Mikkel Abrahamsen.
 19.10.2016 Pola Kyzioł Podstawy Informatyki The domino problem for self-similar structures by Sebastian Barbieri and Mathieu Sablik We defne the domino problem for tilings over self-similar structures of $Z^d$ given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.
 18.10.2016 Grzegorz Jurdzinski Kryptologia 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. References: [1] Paul C. Kocher, Timing Attacks on Implementations of Diffe-Hellman, RSA, DSS and Other Systems (http://www.cryptography.com/public/pdf/TimingAttacks.pdf) [2] David Brumley, Dan Boneh, Remote Timing Attacks are Practical (https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf) [3] Daniel J. Bernstein, Cache-timing attacks on AES (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf)
 13.10.2016 Krzysztof Barański Optymalizacja Kombinatoryczna Level-Oriented Two-Dimensional Packing Algorithms
 13.10.2016 Grzegorz Bukowiec, Sylwester Klocek Algorytmika Algorytm FKT Rozstrzygnięcie, czy w grafie istnieje skojarzenie, oraz znalezienie takiego skojarzenia są problemami łatwymi obliczeniowo. Liczenie wszystkich skojarzeń jest jednak problemem #P-zupełnym - wielomianowy algorytm na ten problem pociągałby równość P = NP. Istnieje jednak sposób na policzenie skojarzeń dla pewnej klasy grafów - w szczególności, dla wszystkich grafów planarnych. Algorytm taki - zwany od nazwisk twórców algorytmem FKT - wykorzystuje bliski związek między pojęciami (łatwego obliczeniowo) wyznacznika i (trudnego) permanentu macierzy.
 12.10.2016 Adam Polak Informatyka Teoretyczna Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequecnce? For many years the classic Longest Common Subsequecnce problem (LCS) have not seen any significant improvement over the simple quadratic time dynamic programming algorithm, with the current fastest algorithm by Masek and Paterson dating back to 1980. In the meantime numerous related problems were studied, among them the Longest Common (Weakly) Increasing Subsequecnce problem, for which Yang, Huang, and Chao found a quadratic time dynamic programming algorithm. Despite some attempts, their result have not been improved for over a decade. In a recent line of research Abboud, Backurs, and Vassilevska Williams show a reduction from SAT to LCS, proving that LCS cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis is false. During the talk I will present an analogous hardness result for the Longest Common Increasing Subsequecnce problem.
 11.10.2016 Michał Zieliński Kryptologia SafeDeflate: compression without leaking secrets CRIME and BREACH attacks on TLS/SSL leverage the fact that compression ratio is not hidden by encryption to recover content of secrets. We introduce SafeDeflate—a modification of a standard Deflate algorithm which compression ratio does not leak information about secret tokens. The modification is compatible with existing Deflate and gzip decompressors. We introduce a model in which attacker can obtain ciphertexts of arbitrary compressed plaintext containing secret values. Then we prove that SafeDeflate is secure in this model.
 06.10.2016 Bartłomiej Bosek Optymalizacja Kombinatoryczna A new variant of the game of cops and robber The talk presents a joint work of Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak. We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,…,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,d2,…,dk) whose components di=dG(u,vi), i=1,2,…,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localize him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously.
 05.10.2016 Tomasz Kisielewski Podstawy Informatyki Programy które są w stanie przeprowadzać rozumowania o swoich własnościach Proving properties of programs within their language Przedstawię wstępną wersję swojego programu badawczego, mającego na celu umożliwienie dowodzenia własności programów w języku, w którym są napisane. Zacznę od motywacji, opierającej się o pewne rozwiązanie zmodyfikowanego dylematu więźnia, w której graczami są programy mające dostęp do kodu źródłowego drugiego gracza. Następnie przybliżę obecny stan automatycznego dowodzenia faktów o programach, ze szczególnym uwzględnieniem silnie typowanych języków funkcyjnych. Na koniec przedstawię dalekosiężne cele i największe trudności, których należy się spodziewać przy implementacji efektywnych funkcji dowodzących fakty o programach. ====== I will present an initial version of my research program, whose main goal is to enable proving properties about programs within the language they are written in. My motivation is based on a specific solution to the open-source prisoner's dilemma, where the players are programs with access to the other player's source code. After explaining the motivation I will shortly present the current state of automatic proving of programs' properties, with emphasis on strongly typed functional languages. Finally, I will introduce my long term goals and the main challenges one should expect to face when implementing an effective function for proving facts about programs.
 15.06.2016 Piotr Kawałek i Teodor Jerzak Podstawy Informatyki Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability by Antoine Genitrini and Cécile Mailler: This article is motivated by the following satisfiability question: pick uniformly at random an and/or Boolean expression of length n, built on a set of k_n Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence. The fundamental breakthrough of this paper is to generalise the previous results for any (reasonable) sequence of integers which enables us, in particular, to solve the above satisfiability question. We also analyse the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomena.
 09.06.2016 Gwenaël Joret Université Libre de Bruxelles Algorytmiczne Aspekty Kombinatoryki Improved Approximation Algorithms for Hitting 3-Vertex Paths We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Very recently, You, Wang, and Cao described a 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee. This is joint work with Samuel Fiorini and Oliver Schaudt.
 08.06.2016 Kamil Pietruszka Podstawy Informatyki Regular Combinators for String Transformations by Rajeev Alur Adam Freilich Mukund Raghothaman We focus on (partial) functions that map input strings to a monoid such as the set of integers with addition and the set of output strings with concatenation. The notion of regularity for such functions has been defined using two-way finite-state transducers, (one-way) cost register automata, and MSO-definable graph transformations. In this paper, we give an algebraic and machine-independent characterization of this class analogous to the definition of regular languages by regular expressions. When the monoid is commutative, we prove that every regular function can be constructed from constant functions using the combinators of choice, split sum, and iterated sum, that are analogs of union, concatenation, and Kleene *, respectively, but enforce unique (or unambiguous) parsing. Our main result is for the general case of non-commutative monoids, which is of particular interest for capturing regular string-to-string transformations for document processing. We prove that the following additional combinators suffice for constructing all regular functions: (1) the left-additive versions of split sum and iterated sum, which allow transformations such as string reversal; (2) sum of functions, which allows transformations such as copying of strings; and (3) function composition, or alternatively, a new concept of chained sum, which allows output values from adjacent blocks to mix.
 02.06.2016 http://wms.mat.agh.edu.pl/~knmd/index.php/i-konferencja-naukowa-knmd/harmonogram/ Algorytmiczne Aspekty Kombinatoryki Konferencja Studencka na AGH
 01.06.2016 Szymon Borak Informatyka Teoretyczna Polynomial time algorithm for finding Hamiltonian cycles in thin grid graphs In general, Hamiltonian Cycle Problem is NP-complete in triangular and square grids. In "Not being(super)thin or solid is hard: A study of grid Hamiltonicity" Arkin et al. claimed HCP for thin triangular grids and thin square grids to be NP-complete as well. However the arguments they gave are incorrect. In fact we show that thin triangular grids as well as thin square grids always have HC. Moreover we show a linear algorithm for finding a HC in such graphs.
 01.06.2016 Piotr Bejda Podstawy Informatyki PATTERN AVOIDANCE IS NOT P RECURSIVE by SCOTT GARRABRANT AND IGOR PAK Let F \subset S_k be a finite set of permutations and let C_n (F) denote the number of permutations  avoiding the set of patterns F. The Noonan Zeilberger conjecture states that the sequence Cn(F) is P-recursive. We disprove this conjecture. The proof uses Computability Theory and builds on our earlier work [GP1]. We also give two applications of our approach to complexity of computing C_n(F).
 25.05.2016 Kolja Knauer Université Aix-Marseille Informatyka Teoretyczna Orienting triangulations - towards Schynyder woods on orientable surfaces We show that the edges of any triangulation of a closed surface different from the projective plane and the sphere can be oriented such that every vertex has non-zero outdegree divisble by three. This confirms a conjecture of Barát and Thomassen. We will explain why this is a first step towards the generalization of Schynyder woods from the plane to orientable surfaces and what is know about this problem.
 19.05.2016 Miloš Stojaković University of Novi Sad Algorytmiczne Aspekty Kombinatoryki Maker-Breaker games on random graphs Of all types of positional games, Maker-Breaker games are probably the most studied. We will survey the topic of Maker-Breaker games played on random graphs, where positional games on graphs meet some standard random graph models. The pace will be gentle, and we will not assume any particular prior knowledge on either positional games or random graphs.
 18.05.2016 Pola Kyzioł Podstawy Informatyki NP-Completeness of a Combinator Optimization Problem by M. S. Joy and V. J. Rayward-Smith We consider a deterministic rewrite system for combinatory logic over combinators $S,K,I,B,C,S',B'$, and $C'$. Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalizing term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda-expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if they represent the same lambda-expression (up to $\beta$-$\eta$-equivalence). The problem of minimizing the number of reduction steps over equivalent combinator expressions (i.e., the problem of finding the "fastest running" combinator representation for a specific lambda-expression) is proved to be NP-complete by reduction from the "Hitting Set" problem.
 12.05.2016 Barłomiej Bosek Algorytmiczne Aspekty Kombinatoryki Coloring shift-chain hypergraphs
 05.05.2016 Jarosław Grytczuk Algorytmiczne Aspekty Kombinatoryki On some graph coloring problems
 28.04.2016 Wojciech Samotij Tel Aviv University Algorytmiczne Aspekty Kombinatoryki How does a typical finite metric space look like?
 27.04.2016 Michał Zieliński Podstawy Informatyki Beta Reduction is Invariant, Indeed by Beniamino Accattoli and Ugo Dal Lago Slot and van Emde Boas weak invariance thesis states that reasonable machines can simulate each other within a polynomially overhead in time.Is lambda  calculus a reasonable machine? Is there a way to measure the computational complexity of a lambda term? This paper presents the first complete positive answer to this longstanding problem. Moreover, our answer is completely machineindependent and based over a standard notion in the theory of lambda calculus: the length of a leftmost-outermost derivation to normal form is an invariant cost model. Such a theorem cannot be proved by directly relating lambda calculus with Turing machines or random access machines, because of the size explosion problem: there are terms that in a linear number of steps produce an exponentially long output. The first step towards the solution is to shift to a notion of evaluation for which the length and the size of the output are linearly related. This is done by adopting the linear substitution calculus (LSC), a calculus of explicit substitutions modelled after linear logic proof nets and admitting a decomposition of leftmostoutermost derivations with the desired property. Thus, the LSC is invariant with respect to, say, random access machines. The second step is to show that LSC is invariant with respect to the lambda calculus. The size explosion problem seems to imply that this is not possible:having the same notions of normal form, evaluation in the LSC is exponentially longer than in the lambda calculus. We solve such an impasse by introducing a new form of shared normal form and shared reduction, deemed useful. Useful evaluation avoids those steps that only unshare the output without contributing to bata redexes, i.e. the steps that cause the blow-up in size. The main technical contribution of the paper is indeed the definition of useful reductions and the thorough analysis of their properties.
 21.04.2016 Jarosław Grytczuk Algorytmiczne Aspekty Kombinatoryki On some problems in combinatorial number theory
 20.04.2016 Adam Polak Informatyka Teoretyczna On subposets of dimension two We study the maximum guaranteed size of a dimension two subposet of an n-element poset. A trivial lower bound of the order of n^{1/2} follows from the Dilworth's theorem. We show an upper bound of the order of n^{2/3} improving the n^{0.8295} result by Reiniger and Yeager. We also discuss promising methods for achieving a better lower bound.
 20.04.2016 Wojciech Kruk Podstawy Informatyki On the equivalence of different presentations of Turner's bracket abstraction algorithm by Lukasz Czajka Turner's bracket abstraction algorithm is perhaps the most well-known improvement on simple bracket abstraction algorithms. It is also one of the most studied bracket abstraction algorithms. The definition of the algorithm in Turner's original paper is slightly ambiguous and it has been subject to different interpretations. It has been erroneously claimed in some papers that certain formulations of Turner's algorithm are equivalent. In this note we clarify the relationship between various presentations of Turner's algorithm and we show that some of them are in fact equivalent for translating lambda-terms in beta-normal form.