# Seminaria

 23.01.2019 12:14 Podstawy Informatyki canceled
 23.01.2019 16:15 Lech Duraj Informatyka Teoretyczna A sub-quadratic algorithm for Longest Common Increasing Subsequence The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated longest common subsequence (LCS). For LCIS, as well as for LCS, there is an O(n2) algorithm and a SETH-based quadratic lower bound. Both the algorithm and the proof of the bound are, however, quite different for LCIS. For LCS, there is also the Masek-Paterson O(n2/log n) algorithm. Its technique (the 'four Russians trick') does not seem to work for LCIS in any obvious way, so a natural question arises: does any sub-quadratic algorithm exist for Longest Common Increasing Subsequence problem? We answer this question positively, presenting a O(n2/logan) algorithm for some a>0. The algorithm is not based on memorizing small inputs (often used for logarithmic speedups, including LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.
 27.02.2019 16:15 Michał Wrona Informatyka Teoretyczna TBA
 13.03.2019 16:15 Tomasz Krawczyk Informatyka Teoretyczna TBA

# Poprzednie referaty

 17.01.2019 14:00 Katarzyna Bułat, Kamil Rajtar Algorytmika Correctness of constructing optimal alphabetic trees reviseted Prezentowana przez nas praca przedstawia nowe obserwacje, które pozwoliły autorom dowieść poprawności dwóch znanych algorytmów (Hu-Tuckera i Garsi-Wachs) na konstrukcję optymalnych drzew utrzymujących porządek leksykograficzny. Omówimy uogólnioną wersję algorytmu Garsi-Wachs wraz z przejrzystym i łatwym do zilustrowania dowodem, który pomaga również w zrozumieniu podejścia Hu-Tuckera.
 16.01.2019 16:15 Grzegorz Gutowski Informatyka Teoretyczna Entropy Compression for Acylic Edge-Colorings Let G be a graph with maximum degree d. We show a randomized procedure that colors the edges of G so that: every two adjacent edges get two different color; edges of every cycle get at least three different colors. Such a coloring is called an acylic edge-coloring of G. The minimum number of colors in an acyclic edge coloring of G is called the acylic index of G. It is conjectured that acylic index of G is at most d+2. We are able to prove that our coloring procedure succeeds for roughly 3.97d colors (improving on a previous result that used 4d colors). This is joint work with Jakub Kozik and Xuding Zhu.
 16.01.2019 12:14 Rafał Byczek i Paweł Mader Podstawy Informatyki A theory of linear typings as flows on 3-valent graphs by Noam Zeilberger Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or “maps”), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classical notion of an abelian group-valued “flow” on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3-valent graph with boundary) valued in a more general algebraic structure consisting of a preordered set equipped with an “implication” operation and unit satisfying composition, identity, and unit laws. Interesting questions and results from the theory of flows (such as the existence of nowhere-zero flows) may then be re-examined from the standpoint of lambda calculus and logic. For example, we give a characterization of when the local flow relations (across vertices) may be categorically lifted to a global flow relation (across the boundary), proving that this holds just in case the underlying map has the orientation of a lambda term. We also develop a basic theory of rewriting of flows that suggests topological meanings for classical completeness results in combinatory logic, and introduce a polarized notion of flow, which draws connections to the theory of proof-nets in linear logic and to bidirectional typing.
 15.01.2019 16:15 Marcin Briański Algorytmy Randomizowane i Aproksymacyjne Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz)
 10.01.2019 14:00 Bartłomiej Jachowicz, Mateusz Kaczmarek Algorytmika SETH-based Lower Bounds for Subset Sum and Bicriteria Path Głównym rezultatem tego artykułu jest ścisła redukcja z k-SAT do problemu Subset Sum na gęstych instancjach, co pokazuje że algorytm Bellmana z 1962 roku O*(T) - dla Subset Sum z n liczbami i celem równym T nie da się poprawić do czasu T1 - e * 2o(n), dla dowolnego e > 0, pod warunkiem prawdziwości SETH. Wnioskiem z tego jest twierdzenie "Direct-OR" dla problemu Subset Sum pod warunkiem prawdziwości SETH, dające nowe możliwości udowadniania dolnych ograniczeń. Daje nam to możliwość założenia, że podjęcie decyzji o tym, czy jedna z N danych instancji problemu Subset Sum jest TAK-instancją wymaga (NT)1-o(1) czasu. Zastosowaniem danego rezultatu jest dolne ograniczenie dla problemu BICRITERIA s,t-PATH pod warunkiem prawdziwośći SETH.
 09.01.2019 12:14 Krzysztof Turowski Purdue University, USA Podstawy Informatyki Compression of Dynamic Graphs Generated by a Duplication Model One of the important topics in the information theory of non-sequential random data structures such as trees, sets, and graphs is the question of entropy: how many bits on average are needed to describe the structure. Here we consider dynamic graphs generated by a duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We provide asymptotic formulas for entopies for both labeled and unlabeled versions of such graphs and construct compression algorithms matching these bounds up to two bits. Moreover, as a side result, we were able to derive asymptotic expansions of expected value of f(X) for functions of polynomial growth, when X has beta-binomial distribution - which in turn allowed to obtain e.g. asymptotic formula the entropy for a Dirichlet-multinomial distribution.
 08.01.2019 16:15 Bartosz Wodziński Algorytmy Randomizowane i Aproksymacyjne Algorithmic barriers from phase transitions (Dimitris Achlioptas, Amin Coja-Oghlan)
 03.01.2019 14:00 Rafał Kaszuba, Krzysztof Zysiak Algorytmika Fast Modular Subset Sum using Linear Sketching Dostając zbiór n dodatnich liczb całkowitych, problem Modular Subset Sum polega na sprawdzeniu czy istnieje podzbiór, który sumuje się do zadanego t modulo dana liczba całkowita m. Jest to naturalne uogólnienie problemu Subset Sum (m=+∞), który silnie łączy się z addytywną kombinatoryką i kryptografią. Niedawno zostały opracowane efektywne algorytmy dla przypadku niemodularnego, działające w czasie blisko-liniowym pseudo-wielomianowym. Jednak dla przypadku modularnego najlepszy znany algorytm (Koiliaris'a i Xu) działa w czasie Õ(m5/4). W tej pracy prezentujemy algorytm działający w czasie Õ(m), który dopasowuje się do warunkowego ograniczenia dolnego opartego na SETH. W przeciwieństwie do większości poprzednich wyników związanych z problemem Subset Sum, nasz algorytm nie korzysta z FFT. Natomiast, jest zdolny zasymulować "podręcznikowe" programowanie dynamiczne znacznie szybciej, używając pomysłów ze Szkicowania Liniowego. Jest to jedna z pierwszych aplikacji technik bazujących na szkicowaniu, by osiągnąć szybki algorytm dla problemów kombinatorycznych w modelu offline.
 19.12.2018 16:15 Agnieszka Łupińska University of California, Davis Informatyka Teoretyczna Gunrock: GPU Graph Analytics Gunrock is a CUDA library for graph-processing designed specifically for the GPU. It uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge.
 19.12.2018 12:14 Jakub Łabaj i Gabriela Czarska Podstawy Informatyki Programming Languages Capturing Complexity Classes by LARS KRISTIANSEN and PAUL J. VODA We investigate an imperative and a functional programming language. The computational power of fragments of these languages induce two hierarchies of complexity classes. Our first main theorem says that these hierarchies match, level by level, a complexity-theoretic alternating space-time hierarchy known from the literature. Our second main theorems says that a slightly different complexity-theoretic hierarchy (the Goerdt-Seidl hierarchy) also can be captured by hierarchies induced by fragments of the programming languages. Well known complexity classes like LOGSPACE, LINSPACE, P, PSPACE  etc., occur in the hierarchies.
 18.12.2018 16:15 Maciej Czerwiński Algorytmy Randomizowane i Aproksymacyjne Lovasz meets Weisfeiler and Leman (by Dell, Grohe and Rattan) "In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k -dimensional generalization known as the Weisfeiler-Leman algorithm."
 13.12.2018 16:15 Vladyslav Hlembotskyi Optymalizacja Kombinatoryczna EERTREE: An Efficient Data Structure for Processing Palindromes in Strings A palindrome is a string which reads the same forward as backward, such as Ada or lol. We will present a data structure which stores information about all the different palindromic substrings of a given string and prove some basic facts about the data structure. We will show that it is useful and discuss some problems which can be solved with it. Mikhail Rubinchik, Arseny M. Shur. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. arXiv, pages 1-21, 2015.
 13.12.2018 14:00 Łukasz Miśkiewicz, Adam Pardyl Algorytmika Space-Efficient Algorithms for Longest Increasing Subseqence Najdłuższy rosnący podciąg jest znanym problemem, który można rozwiązać w złożoności O(n*log(n)) używając O(n*log(n)) dodatkowych bitów. Autorzy pracy prezentują algorytmy korzystające z mniejszej ilości dodatkowej pamięci. Konkretniej, dla sqrt(n) <= s <= n, pokazują sposób obliczania długości najdłuższego rosnącego podciągu w O(1/s * n2 * log(n)) korzystając z O(s * log(n)) dodatkowych bitów oraz obliczanie tego podciągu w czasie O(1/s * n2 * log2(n)) używając tyle samo dodatkowych bitów. Dodatkowo autorzy dowodzą, że dla danej złożoności pamięciowej złożoności czasowe w modelu dostępu sekwencyjnego są optymalne z dokładnością do czynników polilogarytmicznych.
 12.12.2018 16:15 Łukasz Lachowski Informatyka Teoretyczna Complexity of the quorum intersection property of the Federated Byzantine Agreement System A Federated Byzantine Agreement System is defined in the paper https://www.stellar.org/papers/stellar-consensus-protocol.pdf as a pair (V,Q) consisting of a set of nodes V and a quorum function Q : V → P(P(V)) specifying for each node a nonempty family of subsets of nodes, called quorum slices. A subset of nodes is a quorum if and only if for each of its nodes it also contains at least one of its quorum slices. The Disjoint Quorums Problem answers the question whether a given instance of fbas contains two quorums that have no nodes in common. We show that this problem is NP-complete. We also study the problem of finding a quorum of minimal size and show it is NP-hard. Further, we consider the problem of checking whether a given subset of nodes contains a quorum for some selected node. We show this problem is P-complete and describe a method that solves it in linear time with respect to number of nodes and the total size of all quorum slices. Moreover, we analyze the complexity of some of these problems using the parametrized point of view.
 12.12.2018 12:14 Dominik Gryboś Podstawy Informatyki Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus by Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k \geq 0, is given, by a type assignment system for a stratified lambda - calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.
 06.12.2018 16:00 Jakub Nowak Optymalizacja Kombinatoryczna Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies Consensus is one of the most important goals to be achieved when many distributed computers share the same task and resources. There are two main families of algorithms solving this problem. Traditional consensus protocols require O(n2) communication, while blockchains rely on proof-of-work. In this talk we will introduce a new family of leaderless Byzantine fault tolerance protocols, built on a metastable mechanism. These protocols provide a strong probabilistic safety and are both quiescent and green. We will analyze some of their properties and guarantees. Finally we will see results of porting Bitcoin transactions to the introduced family of protocols. Team Rocket. Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies. 2018.
 05.12.2018 12:14 Bartłomiej Puget Podstawy Informatyki THE SAFE LAMBDA CALCULUS by WILLIAM BLUM AND LUKE ONG Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe lambda calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed lambda calculus. In contrast to the original definition of safety, our calculus does not constrain types (to be homogeneous). We show that in the safe lambda calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen. We also propose an adequate notion of beta-reduction that preserves safety. In the same vein as Schwichtenberg’s 1976 characterization of the simply-typed lambda calculus, we show that the numeric functions representable in the safe lambda calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a characterization of representable word functions. We then study the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by P-incrementally justified strategies. Consequently pointers in the game semantics of safe lambda terms are only necessary from order 4 onwards.
 29.11.2018 16:00 Jan Derbisz Optymalizacja Kombinatoryczna Choosability of Planar Graphs Colorability and choosability of planar graphs have been heavily studied in the past. In 1994 Thomassen proved that every planar graph is 5-choosable using concise induction. Recently Grytczuk and Zhu used similar ideas to prove that for every planar graph G we can find a matching M in it such that G-M is 4-choosable with the help of Combinatorial Nullstellensatz theorem.
 29.11.2018 14:00 Konrad Deka, Szymon Kapała Algorytmika Tighter Connections Between Formula-SAT and Shaving Logs W 2015, Abboud, Backurs i Vassilevska-Williams pokazali że algorytm dla LCS działający w czasie O(n2-eps) implikowałby szybki  algorytm dla CNF-SAT, i tym samym fałszywość SETH. W tej pracy, na podstawie innych hipotez dotyczących SAT, autorzy szukają dolnych ograniczeń postaci O(n2/logc n) dla LCS, a także problemu odległości Frecheta oraz problemu matchowania regexów. Głównym rezultatem jest redukcja z SAT-a na formule wielkości s, mającej n zmiennych, do LCS na ciągach długości 2n/2s1+o(1). Wynika stąd, że algorytm dla LCS działający w O(n2/log7+epsn) implikowałby fałszywość pewnych hipotez o Formula-SAT, a algorytm działający w O(n2/log17+epsn) - znaczący postęp w teorii złożoności obwodów.
 28.11.2018 16:15 05.12.2018 16:15 Piotr Kawałek Informatyka Teoretyczna Computational approach to solving equations in finite realms Computational approach to the problem of solving equation, began with the question of David Hilbert. He asked, if there exists an algorithm, that decides wheather given Diophantine equation has a solution or not.  Yuri Matiyasevich proved this problem to be undecidable.  An analogy for decidability in finite realms is tractability. During the talk, we introduce the notion of PolSat problem for finite algebras and discuss the results for the wide class of algebraic structures.
 28.11.2018 12:14 Jacek Kurek i Bruno Pitrus Podstawy Informatyki COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PA The subject of enumerative combinatorics is both classical and modern. It is classical, as the basic counting questions go back millennia; yet it is modern in the use of a large variety of the latest ideas and technical tools from across many areas of mathematics. The remarkable successes from the last few decades have been widely publicized; yet they come at a price, as one wonders if there is anything left to explore. In fact, are there enumerative problems that cannot be resolved with existing technology? In this paper we present many challenges in the field from the computational complexity point of view, and describe how recent results fit into the story.
 27.11.2018 16:15 04.12.2018 16:15 Dominika Salawa, Kamil Kropiewnicki Algorytmy Randomizowane i Aproksymacyjne Representative sets in matroids (based on chapter of 'Parameterized algorithms')
 22.11.2018 16:00 Krzysztof Maziarz Optymalizacja Kombinatoryczna A refinement of choosability of graphs Between the well-known concepts of k-colorability and k-choosability (also know as k-list colorability) lies a whole spectrum of more refined notions. This allows for seeing k-colorability and k-choosability under one unified framework. Exploring this, one immediately discovers interesting problems - for example, possible strengthenings of the four color theorem. We will take a look at these notions, prove some of their properties, and leave many conjectures and open problems.
 22.11.2018 14:00 Rafał Byczek, Bruno Pitrus Algorytmika Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów. Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2-δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym. W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)).
 21.11.2018 12:14 Marcin Briański Podstawy Informatyki On the compressibility of finite languages and formal proofs by Sebastian Eberhard and Stefan Hetzl We consider the minimal number of productions needed for a grammar to cover a finite language L as the grammatical complexity of L. We study this measure for several types of word and tree grammars and show that it is closely connected to well-known measures for the complexity of formal proofs in first-order predicate logic. We construct an incompressible sequence of finite word languages and transfer this and several other results about the complexity of word and tree languages to formal proofs
 20.11.2018 16:15 Dawid Tracz Algorytmy Randomizowane i Aproksymacyjne Finding Cliques in Social Networks: A New Distribution-Free Model (Fox, Roughgarden, Seshadhri, Wei, Wein)
 15.11.2018 16:00 Jakub Łabaj Optymalizacja Kombinatoryczna Contracting a Planar Graph Efficiently Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, Piotr Sankowski: Contracting a Planar Graph Efficiently. CoRR abs/1706.10228 (2017) Jakub Łabaj. Contracting a Planar Graph Efficiently. slides. 2018.
 15.11.2018 14:00 Tomasz Zieliński, Michał Zwonek Algorytmika On the Complexity of the (Approximate) Nearest Colored Node Problem Mając dany graf G = (V, E) gdzie każdy wierzchołek ma przypisany kolor, pytamy o przybliżoną odległość pomiędzy danym wierzchołkiem v a najbliższym jemu kolorowi c. Prezentujemy wyrocznię o rozciągłości 4k-5 wykorzystującą O(kn sigma^(1/k)) przestrzeni i O(log k) czasu zapytania. Następnie dowodzimy, że posiadając estymatę rzędu O(polylog(n)) jesteśmy w stanie w czasie O(1) udzielić odpowiedzi na pytanie o dokładną odległość dist(v, c). Na końcu pokazujemy związek pomiędzy problemem lambda-OuMv a odległością dist(v, c).
 14.11.2018 16:15 21.11.2018 16:15 Michał Seweryn Informatyka Teoretyczna Bumping a ladder We show that every 3-connected graph which contains many disjoint 2xn-grid minors, contains a 2x(n+1)-grid-minor. We use this result in a qualitative structure theorem for graphs without large 2xn grids. This is a result from a joint paper with Tony Huynh, Gwenaël Joret, Piotr Micek and Paul Wollan
 14.11.2018 12:14 Mateusz Tokarz Podstawy Informatyki Enumerating Proofs of Positive Formulae by GILLES DOWEK AND YING JIANG We provide a semi-grammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proof-term of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F.
 13.11.2018 16:15 Mateusz Pabian Algorytmy Randomizowane i Aproksymacyjne New approximation algorithm for (1,2)-TSP (Adamaszek, Mnich, Paluch)
 08.11.2018 16:15 Marcin Muszalski Optymalizacja Kombinatoryczna On the queue-number of graphs with bounded tree-width In this talk I will present upper bound for a queue-number of graphs with bounded tree-width obtained by Veit Wiechert. The new upper bound, 2k - 1, improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. Additionally I will show his construction of k-trees that have queue-number at least k + 1. The construction solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queue-number of 2-trees is equal to 3. Veit Wiechert. On the queue-number of graphs with bounded tree-width. Electronic Journal of Combinatorics, 24(1):1-14, 2017. Marcin Muszalski. Queue-number of graphs with bounded tree-width - Veit Wiechert. slides. 2018.
 08.11.2018 14:00 Weronika Grzybowska, Paweł Mader Algorytmika Hamming distance completeness and sparse matrix multiplication Autorzy prezentują polilogarytmiczne redukcje pomiędzy obliczaniem odległości Hamminga a iloczynem skalarnym, w którym miejsce mnożenia zajmuje pewna funkcja binarna na liczbach całkowitych. Dla takich funkcji binarnych należą dominance product, threshold product i odległości l_{2p+1} dla stałego p. Wykorzystując wyżej opisane redukcje, autorzy wykazują równość (z dokładnością do czynników polilogarytmicznych) złożoności wyliczania  powyższych funkcji dla dwóch zbiorów wektorów. Dodatkowo, autorzy dowodzą, że APHam (oraz ten sam problem z użyciem innych wymienionych funkcji) mieści się w czasie polilogarytmicznym od mnożenia macierzy rozmiaru n na nd i nd na n, zawierających po nd niezerowych wartości.
 07.11.2018 12:14 Paweł Palenica Podstawy Informatyki On Randomised Strategies in the λ-Calculus by Ugo Dal Lago and Gabriele Vanoni In this work we introduce randomized reduction strategies - a notion already studied in the context of abstract reduction systems - for the lambda-calculus. We develop a simple framework that allows us to prove if a probabilistic strategy is positive almost-surely normalizing. Then we propose a simple example of probabilistic strategy for the lambda-calculus that has such a property and we show why it is non-trivial with respect to classical deterministic strategies such as leftmost-outermost or rightmostinnermost. We conclude studying this strategy for two classical sub- lambda calculi, namely those duplication and erasure are syntactically forbidden.
 06.11.2018 16:15 Szymon Łukasz Algorytmy Randomizowane i Aproksymacyjne NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (A. Bhangale) We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices, 1) It is NP-hard to color it with log^delta n colors for some delta>0. 2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.
 31.10.2018 12:14 Rafał Burczyński Podstawy Informatyki A Hitchhiker’s Guide to descriptional complexity through analytic combinatorics by Sabine Broda, António Machiavelo, Nelma Moreira and Rogério Reis Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several $\epsilon-NFA$ constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the $\epsilon-NFA$ constructions approaches the corresponding $\epsilon-free NFA$ construction, asymptotically and on average.
 30.10.2018 16:15 Wiktor Daniec Algorytmy Randomizowane i Aproksymacyjne David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5) David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
 25.10.2018 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna A new variant of the game of cops and robber 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,2,...,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 localise 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. The aim of the talk is to present results concerning 2-trees, outerplanar graphs and planar graphs. This is a joint work with Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, and Małgorzata Śleszyńska-Nowak. Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Centroidal localization game. arXiv, pages 1-15, 2017. Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Localization game on geometric and planar graphs. arXiv, pages 1-15, 2017.
 25.10.2018 14:00 Filip Bartodziej, Vladyslav Hlembotskyi Algorytmika Fine-grained Lower Bounds on Cops and Robbers Sumienni policjanci, czy sprytny złodziej? Na tym seminarium dowiemy się kto triumfuje, jak szybko (lub jak wolno) jesteśmy w stanie się o tym przekonać i ilu policjantów wystarczy, aby przyskrzynić nawet samego Frank’a Abagnale’a. Rozważania bedą oparte o grę strategiczna w policjantów i złodziei na grafie (cops and robbers). Uzyskane wyniki opierają sie na założeniu SETH/ETH.
 24.10.2018 12:14 Szymon Stankiewicz Podstawy Informatyki Encoding Turing Machines into the Deterministic Lambda Calculus by Ugo Dal Lago and Beniamino Accattoli This note is about encoding Turing machines into the lambda -calculus. The encoding we show is interesting for two reasons: 1. Weakly strategy independent : the image of the encoding is a very small fragment of the lambda - calculus, that we call the deterministic lambda -calculus det. Essentially, it is the CPS (continuation-passing style) lambda -calculus restricted to weak evaluation (i.e., not under abstractions). In det every term has at most one redex, and so all weak strategies collapse into a single deterministic evaluation strategy, because there are no choices between redexes to be made. The important consequence of this property is that every weak evaluation strategy then allows to simulate Turing machines,as well as any strong strategy reducing weak head redexes (or even only weak head redexes) first. 2. Linear overhead: the simulation is very efficient, when taking the number of beta-steps as the time cost model for the deterministic lambda -calculus. The simulation in det indeed requires a number of beta-steps that is linear in the number of transitions of the encoded Turing machine, which is the best possible overhead. Therefore, not only all weak strategies simulate Turing machines, but they all do it efficiently.
 18.10.2018 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Local Dimension is Unbounded for Planar Posets In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter. Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017.
 18.10.2018 14:00 Jan Mełech, Rafał Burczyński Algorytmika A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum Celem znanego problemu NP-zupełnego Subset-Sum jest znalezienie takiego podzbioru multizbioru o mocy n, którego suma elementów wynosi t. Autorzy prezentują krótkie probabilistyczne rozwiązanie bazujące na szybkiej transformacie Fouriera oraz manipulacjach na funkcjach tworzących działające w czasie O((n+t)*polylog(t)) i zwracające odpowiedź z prawdopodobieństwem błędu rzędu O(1/(n+t)). Ten wynik został osiągnięty wcześniej, jednak praca upraszcza rozwiązanie, zawierając je raptem w kilku stronach.
 17.10.2018 16:15 24.10.2018 16:15 Patryk Mikos Informatyka Teoretyczna Does the representation matter? The class of unit interval graphs has at least 3 equivalent definitions: intersection graphs of unit-length intervals, intersection graphs of intervals such that no interval properly contains any other interval, K1,3-free chordal graphs. We ask whether the competitive ratio in the online unit-interval graph coloring with bandwidths depends on the chosen graph representation.
 17.10.2018 12:14 Vladyslav Hlembotskyi Podstawy Informatyki Limited Automata and Regular Languages by Giovanni Pighizzini and Andrea Pisoni Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d \geq 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schutzenberger representation for context-free languages, we present a new conversion from context-free languages into 2-limited automata.
 11.10.2018 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna A Tight Bound for Shortest Augmenting Paths on Trees The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound. This is a joint work with Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz. Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz. A Tight Bound for Shortest Augmenting Paths on Trees. arXiv, pages 1-22, 2017.
 11.10.2018 14:00 Dawid Pyczek, Michał Zieliński Algorytmika On the Worst-Case Complexity of TimSort TimSort jest bardzo interesującym algorytmem sortującym, który został wprowadzony do Pythona stosunkowo niedawno, bo w 2002 roku. Ten bardzo popularny algorytm używany jest z powodzeniem na całym świecie. Wynika to z faktu, że działa on wyjątkowo szybko na częściowo posortowanych danych. Aż do niniejszej pracy nie była znana pesymistyczna złożoność tego algorytmu -- w pracy pokazane zostanie, że pesymistyczna złożoność algorytmu TimSort wynosi O(n log n). Następnie złożoność algorytmu ograniczymy przez O(n+n log ρ), gdzie ρ to ilość przebiegów. Pierwsza złożoność w bezpośredni sposob wynika z drugiej, ale oba dowody są ciekawe i pomagają lepiej zrozumieć działanie TimSorta. Dodatkowo w wyniku analizy algorytmu autorzy pracy odryli błąd w implementacji TimSorta w Javie.
 10.10.2018 16:15 Andrzej Dorobisz Informatyka Teoretyczna Induced subgraphs of graphs with large chromatic number Based on the paper Induced subgraphs of graphs with large chromatic number. III. Long holes by Maria Chudnovsky, Alex Scott and Paul Seymour a proof of a 1985 conjecture of Gyarfas that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ will be presented.
 10.10.2018 12:14 Michał Zieliński Podstawy Informatyki Lambda Theories allowing Terms with a Finite Number of Fixed Points by BENEDETTO INTRIGILA and RICHARD STATMAN A natural question in the lambda calculus asks what is the possible number of fixed points of a combinator (closed term). A complete answer to this question is still missing (Problem 25 of TLCA Open Problems List) and we investigate the related question about the number of fixed points of a combinator in lambda-theories. We show the existence of a recursively enumerable lambda theory where the number is always one or infinite. We also show that there are lambda-theories such that some terms have only two fixed points. In a first example, this is obtained by means of a non-constructive (more precisely non-r.e.) lambda-theory where the range property is violated. A second, more complex example of a non-r.e. Lambda-theory (with a higher unsolvability degree) shows that some terms can have only two fixed points while the range property holds for every term.
 04.10.2018 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Some open problems
 03.10.2018 12:14 Jarosław Duda Instytut Informatyki UJ Podstawy Informatyki Krótkie wprowadzenie do ANS, MERW i pól Markova Na seminarium spróbuję zainteresować kilkoma z tematów, którymi się zajmowałem, np. kodowaniem Asymmetric Numeral Systems, które jest obecnie używane w produktach m.in. Apple, Facebook, Google. Opowiem też o Maximal Entropy Random Walk, czyli jak optymalnie wybierać błądzenie przypadkowe na grafie - z perspektywy zastosowań m.in. do maksymalizacji ilości przechowywanej informacji, zrozumienia i naprawienia rozbieżności między dyfuzją a mechaniką kwantową, analizy obrazów, sieci społecznych, czy rekonstrukcji traktów nerwowych. Tematem łączącym powyższe będą pola Markova, czyli wielowymiarowe uogólnienie procesów Markova, o których też krótko opowiem z przykładem zastosowania do poprawienia pojemności dysków twardych. Slajdy do seminarium można znaleźć na: http://tiny.cc/2jpiyy
 14.06.2018 16:15 Mateusz Twaróg, Patryk Urbański, Łukasz Majcher Optymalizacja Kombinatoryczna Progress in the Arachne Project
 13.06.2018 12:14 Marcin Briański Podstawy Informatyki COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS by DENIS HIRSCHFELDT, CARL JOCKUSCH, RUTGER KUYPER, AND PAUL SCHUPP A coarse description of a set A \subset \omega  is a set D \subset \omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1- genericity in place of weak 2-randomness. In the other direction, we show that if A \leq_T \emptyset is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set.
 07.06.2018 17:15 Krzysztof Maziarz Optymalizacja Kombinatoryczna The chromatic number of the plane is at least 5​ The Hadwiger-Nelson problem asks for the minimum number of colors required to color the plane, in such a way, that any two points at distance exactly one are assigned different colors. Albeit its simple definition, no significant progress on the question was made for nearly a century. In the discussed paper, Aubrey D. N. J. de Grey has shown a set of points in the plane, such that 5 colors are necessary to color it properly, thus improving a long-standing lower bound of 4 colors. Interestingly, the smallest such set discovered so far has 1581 vertices. The chromatic number of the plane is at least 5, Aubrey D.N.J. de Grey
 07.06.2018 16:15 Szymon Łukasz Optymalizacja Kombinatoryczna Dynamic F-free Coloring of Graphs An F-free coloring is a coloring of a graph such that each color induces an F-free graph. In this talk we consider dynamic F-free coloring which can be interpreted as a game of Presenter and Painter. In each move Presenter presents new vertices along with the edges between them and already known vertices. In the same move Presenter can also discolor arbitrary vertices and request Painter to color some vertices. The problem we consider can be stated as follows: For a given graph G, is there a sequence of moves for which the greedy algorithm uses at least k colors during dynamic F-free coloring of G. We will show that for some classes of graphs this problem is decidable in polynomial time (for fixed F and k) in the case where F is 2-connected or F is path of length 2. Piotr Borowiecki, Elżbieta Sidorowicz, Dynamic F-free Coloring of Graphs, Graphs and Combinatorics 2018, Volume 34, Issue 3, pp 457-475
 06.06.2018 12:14 Bruno Pitrus Podstawy Informatyki Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.
 30.05.2018 16:15 06.06.2018 16:15 Grzegorz Herman Informatyka Teoretyczna Relational parsing: a clean generalized parsing algorithm. We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.
 30.05.2018 12:14 Bartłomiej Puget Podstawy Informatyki STATMAN'S HIERARCHY THEOREM by BRAM WESTERBAAN, BAS WESTERBAAN, RUTGER KUYPER, CARST TANKINK, REMY VIEHOFF AND HENK BARENDREGT In the Simply Typed lambda calculus Statman investigates the reducibility relation between types: for types freely generated using \arrow and a single ground type 0, define A \leq B if there exists a lambda definable injection from the closed terms of type A into those of type B. Unexpectedly, the induced partial order is the (linear) well-ordering (of order type) \omega + 4.
 24.05.2018 16:15 Marcin Briański Optymalizacja Kombinatoryczna How many ants does it take to find the food? In this talk we will consider the ANTS (Ants Nearby Treasure Search) problem: consider n agents (ants), controlled by finite automata (or PDAs) exploring an infinite grid attempting to locate a hidden treasure. The question we want to answer is: how many agents are necessary to accomplish this task in (expected) finite time? Of course, the answer will depend on the way we model this situation. We will consider synchronous as well as asynchronous environment, agents with access to randomness as well as deterministic ones, agents controlled by PDA as well as finite automata and various combinations thereof. In most cases established bounds are tight, however in certain cases there is still ample room for improvement (which some might consider interesting). Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, Roger Wattenhofer, How many ants does it take to find the food?, Theoretical Computer Science Volume 608, Part 3, 10 December 2015, Pages 255-267
 23.05.2018 12:14 Podstawy Informatyki Canceled
 17.05.2018 16:15 Marcin Muszalski Optymalizacja Kombinatoryczna On the Number of Maximum Empty Boxes Amidst n Points I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S. They created first superlinear lower bound for the number of maximum-volume empty boxes amidst n points in R d (d ≥ 3). I would like to present it and show a prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log(n) 2^α(n) ), where α(n) is the extremely slowly growing inverse of Ackermann’s function. The previous best bound for this problem, O(n^2 ), is due to Naamad, Lee, and Hsu (1984). Adrian Dumitrescu, Minghui Jiang, On the Number of Maximum Empty Boxes Amidst n Points, Discrete & Computational Geometry, Volume 59 (3), 742-756, 2018
 16.05.2018 12:14 Maciej Czerwiński Podstawy Informatyki On Type Inference in the Intersection Type Discipline by Gerard Boudol and Pascal Zimmer We introduce a new unification procedure for the type inference problem in the intersection type discipline. We show that unification exactly corresponds to reduction in an extended  lambda calculus, where one never erases arguments that would be discarded by ordinary β-reduction. We show that our notion of unification allows us to compute a principal typing for any strongly normalizing lambda expression.
 10.05.2018 16:15 Jakub Szarawski Optymalizacja Kombinatoryczna Faster approximation schemes for the two-dimensional knapsack problem In 2008 Klaus Jansen and Roberto Solis-Oba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented. S. Heydrich, A. Wiese, Faster approximation schemes for the two-dimensional knapsack problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 79-98
 09.05.2018 12:14 Dominika Salawa Podstawy Informatyki The Hiring Problem and Permutations by Margaret Archibald and Conrado Martínez The hiring problem has been recently introduced by Broder et al. in last year’s ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem.
 26.04.2018 16:15 Sylwester Klocek Optymalizacja Kombinatoryczna Colouring of (P3∪P2)-free graphs In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs. Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)-free graphs, Graphs and Combinatorics, Volume 34 (1), 2018
 25.04.2018 16:15 Jacek Krzaczkowski Informatyka Teoretyczna Complexity of solving equations Solving equations  is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider  equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is  obviously decidable in nondeterministic polynomial time. The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on  the polynomial  equivalence problem in which we ask whether two polynomials over  a finite algebra describe the same function.   This is joint work with Paweł M. Idziak and Piotr Kawałek..
 25.04.2018 12:00 Rafał Burczyński Podstawy Informatyki How to select a loser Consider the following game: everyone from a group of n people flips a coin with result either 0 or 1, both equally probable; if no one gets a 0, the round is repeated, otherwise people with 1's are considered "winners" and the game continues only with participants who got 0's. The process continues until there is one person left, who is called "loser". We can picture this process as a binary tree and analyze some of its properties in average case. The analysis is not completely trivial, in particular one may find application for tools such as Mellin transform.
 19.04.2018 16:15 Grzegorz Jurdziński Optymalizacja Kombinatoryczna Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles. Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109
 18.04.2018 12:00 Rafał Burczyński Podstawy Informatyki Mellin transforms and asymptotics We will introduce Mellin transform, which may be used for the asymptotic analysis of a particular class of sums. I will start with basic properties and then present fundamental correspondence between the asymptotic expansion of a function at 0 or infinity and singularities of its transform. Finally we will show some combinatorial applications of the transform.
 12.04.2018 16:15 Maciej Woźniak Optymalizacja Kombinatoryczna Find Your Place: Simple Distributed Algorithms for Community Detection Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if: G is connected and not bipartite, |V_1| = |V_2| V_1 \cap V_2 = \emptyset Every vertex has degree d Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1, Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2. We define (weak) block reconstruction of graph as two-coloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact. I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for non-regular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities. Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia
 11.04.2018 12:14 Weronika Grzybowska Podstawy Informatyki Average complexity of Moore’s and Hopcroft’s algorithms by Julien David In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore’s state minimization algorithm is O(n log (log n)),  where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hopcroft’s algorithm is characterized, for which the algorithm will be proved to be always faster than Moore’s algorithm. Finally, we present experimental results on the usual implementations of Hopcroft’s algorithm.
 05.04.2018 16:15 Anna Kobak Optymalizacja Kombinatoryczna On tree-partition-width A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2. David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253
 04.04.2018 16:15 Bartosz Walczak Informatyka Teoretyczna Sparse Kneser graphs are Hamiltonian For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of {1, …, n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k + 1, k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥ 3, the odd graph K(2k + 1, k) has a Hamilton cycle. Its construction is based on constructing a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, it provides an alternative proof of the so-called middle levels theorem, originally proved by Mütze in 2014. Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636).
 04.04.2018 12:14 Vladyslav Hlembotskyi Podstawy Informatyki A graph theoretic approach to automata minimality by Antonio Restivo and Roberto Vaglica The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
 28.03.2018 16:15 Grzegorz Guśpiel Informatyka Teoretyczna On the Complexity of Crossing Minimization For a bipartite graph G with vertex bipartition (X, Y), a two-layer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines LX and LY, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a two-layer drawing is a two-layered graph. We study basic graph problems on two-layered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)-path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.   This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi.
 28.03.2018 12:00 Szymon Stankiewicz Podstawy Informatyki Introduction to Higher-Order Categorical Logic - continuation
 22.03.2018 16:15 Aleksandra Mędrek Optymalizacja Kombinatoryczna The Matching Problem in General Graphs is in Quasi-NC Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached. Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017