16.10.2019 16:15
Mikkel Abrahamsen
Københavns Universitet
Informatyka Teoretyczna
Geometric Multicut

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as Geometric k-Cut, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n4 log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2−4/3k)-approximation algorithm.

Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

23.10.2019 16:15
Gwenaël Joret
Université Libre de Bruxelles
Informatyka Teoretyczna
30.10.2019 16:15
Bartosz Walczak
Informatyka Teoretyczna
Coloring and Maximum Weight Independent Set of rectangles

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω). This is the first improvement of the original O(ω2) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, which improves the previous best approximation ratio of O(log n/log log n).

Joint work with Parinya Chalermsook.

13.11.2019 16:15
Grzegorz Guśpiel
Informatyka Teoretyczna
20.11.2019 16:15
Patryk Mikos
Informatyka Teoretyczna
Efficient enumeration of non-isomorphic interval graphs

Poprzednie referaty

19.06.2019 16:15
Bartłomiej Kielak
Informatyka Teoretyczna
Generalized Turán densities and counting cycles in graphs

The Turán number ex(n, H) is the maximum number of edges that an H-free graph on n vertices can have. This quantity is well studied for graphs with chromatic number greater than 2, but the problem of determining it for all bipartite graphs remains open. A generalization of the Turán number, namely, the maximum possible number of copies of a graph T in an H-free graph on n vertices, denoted by ex(n, T, H), is recently attracting a lot of attention. In particular, the problem of determining ex(n, C5, C3), posed by Erdős in 1984, was completely solved in the last few years with the use of the flag algebras method.

In this talk, we will show an elementary proof that ex(n, Ck, Ck−2) = (n/k)k + o(nk) for any odd k > 5.

Joint work with Andrzej Grzesik.

12.06.2019 16:15
Bartosz Walczak
Informatyka Teoretyczna
Subexponential algorithms for finding large induced sparse subgraphs

Let 𝒞 and 𝒟 be hereditary graph classes. Consider the following problem: given a graph G ∈ 𝒟, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to 𝒞. We prove that it is solvable in 2o(n) time, where n is the number of vertices of G, if the following conditions are satisfied:

  • the graphs in 𝒞 are sparse, i.e., they have linearly many edges in terms of the number of vertices;
  • the graphs in 𝒟 admit balanced separators of size governed by their density, e.g., O(Δ) or O(√m), where Δ and m denote the maximum degree and the number of edges, respectively; and
  • the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph.

This leads, for example, to the following corollaries for specific classes 𝒞 and 𝒟:

  • a largest induced forest in a Pt-free graph can be found in 2Õ(n2/3) time, for every fixed t; and
  • a largest induced planar graph in a string graph can be found in 2Õ(n3/4) time.

Joint work with Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, and Erik Jan van Leeuwen.

05.06.2019 12:14
Szymon Stankiewicz
Podstawy Informatyki
Bohm's Theorem, Church's Delta, Numeral Systems, and Ershov Morphisms by Richard Statman and Henk Barendregt
In this note we work with untyped lambda terms under beta-conversion and consider the possibility of extending Bohm's theorem to in¯nite RE (recursively enumerable) sets. Bohm's theorem fails in general for such sets V even if it holds for all finite subsets of it. It turns out that generalizing Bohm's theorem to infnite sets involves three other superfcially unrelated notions; namely, Church's delta, numeral systems, and Ershov morphisms. Our principal result is that Bohm's theorem holds for an infnite RE set V closed under beta conversion iff V can be endowed with the structure of a numeral system withc predecessor iff there is a Church delta (conditional) for V iff every Ershov morphism with domain V can be represented by a lambda term.
04.06.2019 16:15
Jarosław Grytczuk
Politechnika Warszawska
Algorytmy Randomizowane i Aproksymacyjne
Graph polynomials and choosability
A result of Thomassen asserts that every planar graph is 5-choosable (colorable from arbitrary lists of size 5 preassigned to the vertices of a graph). We prove that every planar graph has a matching whose deletion gives a 4-choosable graph. The proof is based on Combinatorial Nullstellensatz - a famous algebraic result of Alon involving multivariable polynomials. We also discuss possible applications of this method to other graph coloring problems, like the four color problem or the empire coloring problem, for instance.
Joint work with Xuding Zhu.
29.05.2019 12:14
Bartłomiej Puget
Podstawy Informatyki
Solving the Rubik’s Cube Optimally is NP-complete by Erik D. Demaine and Sarah Eisenstat
In this paper, we prove that optimally solving an n × n × n Rubik’s Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n×n×n Rubik’s Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik’s Square – an n × n × 1 generalization of the Rubik’s Cube – and then proceed with a similar but more complicated proof for the Rubik’s Cube case. Our results hold both when the goal is make the sides monochromatic and when the goal is to put each sticker into a specific location.
22.05.2019 12:14
Maciej Czerwiński
Podstawy Informatyki
Automata Theoretic Account of Proof Search by Aleksy Schubert, Wil Dekkers and Henk P. Barendregt
Techniques from automata theory are developed that handle search for inhabitants in the simply typed lambda calculus. The resulting method for inhabitant search, which can be viewed as proof search by the Curry-Howard isomorphism, is proven to be adequate by a reduction of the inhabitant existence problem to the emptiness problem for appropriately defined automata. To strengthen the claim, it is demonstrated that the latter has the same complexity as the former. We also discuss the basic closure properties of the automata.
15.05.2019 16:15
Krzysztof Kleiner
Informatyka Teoretyczna
Range queries and counting triangles

Listing and counting triangles in sparse graphs are well-studied problems. For a graph with m edges, Björklund et al. gave an O(m1.408) algorithm which can list up to m triangles. The exact exponent depends on the exponent omega in matrix multiplication, and becomes 4/3 if omega=2. Pătraşcu proved that an algorithm faster than O(m4/3) would imply a sub-quadratic algorithm for 3-SUM, which is considered unlikely.

In our work we consider a variant of triangle problem asking to determine for every edge the number of triangles which contains that edge. We prove that this problem is no easier than listing up to m triangles, although it still admits an algorithm of the same O(m1.408) complexity. We also propose a natural class of range query problems, including for example the following problem: given a family of ranges in an array, compute the number of inversions in each of them. We prove that all the problems in this class are equivalent, under one-to-polylog reductions, to counting triangles for each edge. In particular the time complexities of these problems are the same up to polylogarithmic factors.

This is joint work of Lech Duraj, Krzysztof Kleiner, Adam Polak and Virginia Vassilevska-Williams.

15.05.2019 12:14
Przemysław Rutka (Lublin)
Podstawy Informatyki
Wybrane algorytmiczne zastosowania klasycznych wielomianów ortogonalnych
Klasyczne wielomiany ortogonalne, odpowiadające im klasyczne funkcje wagowe oraz ich własności znajdują wiele zastosowań w takich chociażby obszarach jak tomografia, mechanika kwantowa, kombinatoryka, przetwarzanie obrazów i sygnałów, kompresja danych oraz zwiększanie wydajności algorytmów. W tym ostatnim zakresie cały czas uzyskuje się wiele ciekawych wyników, pozwalających na efektywne numeryczne rozwiązywanie różnych problemów. Można do tych problemów w szczególności zaliczyć barycentryczne interpolacje Fejéra, Hermite'a i Lagrange'a oraz problemy ekstremalne typu Szegő i Markowa-Bernsteina. W pierwszym przypadku, gdy interpolowanych jest n wartości w węzłach, będących zerami klasycznych wielomianów ortogonalnych, możliwa jest poprawa złożoności obliczeniowej algorytmów, obliczających wartości wielomianów interpolacyjnych w oparciu o wzory barycentryczne, z O(n^2) do O(n). Wymagane jest w tym celu zastosowanie odpowiednich jawnych wzorów na wagi barycentryczne lub wzorów wiążących wagi barycentryczne z wagami i węzłami kwadratur Gaussa. Z kolei w drugim przypadku, jak się okazuje powiązanym z pierwszym, daje się sformułować wzory, pozwalające bezpośrednio obliczać na komputerze najlepsze stałe, występujące w nierównościach typu Szegő i Markowa-Bernsteina oraz wartości wielomianów ekstremalnych, dla których te nierówności stają się równościami. Nierówności te związane są z iterowanymi klasycznymi funkcjami wagowymi i można je wykorzystać do szacowania wartości lub norm pochodnych D^{k}p lub różnic progresywnych Δ^{k}p wielomianów p(x), odpowiednio w przypadku ciągłym lub dyskretnym.
     Inne tego typu rezultaty, korzystające z klasycznych wag i/lub klasycznych wielomianów ortogonalnych, można otrzymać także dla problemu typu izoperymetrycznego w klasie płaskich, zamkniętych krzywych wielomianowych, problemu równowagi elektrostatycznej układu ładunków, problemu efektywnej, stabilnej i najbardziej ekonomicznej interpolacji oraz problemu dwustronnych oszacowań aproksymacyjnych a priori typu Chernoffa.
08.05.2019 12:14
Weronika Grzybowska
Podstawy Informatyki
A Mesh of Automata by Sabine Broda, Markus Holzer, Eva Maia, Nelma Moreira, Rogerio Reis
We contribute new relations to the taxonomy of di erent conversions from regular expressions to equivalent nite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (A_POS), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version of the position automaton which plays a similar role as A_POS but now for the reverse expression. Moreover, it turns out that the prefix automaton A_Pre is central to reverse expressions, because the determinisation of the double reversal of A_Pre (first reverse the expression, construct the automaton A_Pre, and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to nite automata seems quite similar, there are signifcant differences.
25.04.2019 16:15
Rafał Byczek
Optymalizacja Kombinatoryczna
The chromatic number of Kneser graphs

In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a brilliant and totally unexpected solution, using the “Borsuk–Ulam theorem” from topology, was found by László Lovász twenty-three years later. It happens often in mathematics that once a proof for a long-standing problem is found, a shorter one quickly follows, and so it was in this case. Within weeks Imre Bárány showed how to combine the Borsuk–Ulam theorem with another known result to elegantly settle Kneser’s conjecture. Then in 2002 Joshua Greene, an undergraduate student, simplified Bárány’s argument even further, and it is his version of the proof that I present here.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

24.04.2019 16:15
Bartłomiej Bosek
Informatyka Teoretyczna
Algorithms for posets and graphs games – coloring and matching

Graph colorings and online algorithms on graphs constitute the key fragments of the algorithmic graph theory. Specifically, the subject of this study will be a presentation of the results concerning

  • different variants of coloring of graphs and partially ordered sets,
  • online coloring of partially ordered sets,
  • incremental matchings of bipartite graphs.

The first part of the talk will concern different aspects of the coloring problem as well as different evidential techniques. The presented results concern majority choosability of digraphs, harmonious coloring of hypergraphs and semi-uni conjecture of product of two posets. The next part of presentation will concern online chain partitioning of posets. There will be presented a full characterization of the class of posets, for which the number of colors (chains) used by first-fit is a function of width, i.e. best offline solution. This part will also present two different subexponential online algorithm for the online chain partitioning problem. The last part will concern the incremental matching problem in bipartite graphs. There will be presented an incremental algorithm that maintains the maximum size matching in total time equal the running time of one of the fastest offline maximum matching algorithm that was given by Hopcroft and Karp. Moreover, I will show an analysis of the shortest augmenting path algorithm.

This is joint work with Marcin Anholcer, Jarosław Grytczuk, Sebastian Czerwiński, Paweł Rzążewski, Stefan Felsner, Kolja Knauer, Grzegorz Matecki, Tomasz Krawczyk, H. A. Kierstead, Matthew Smith, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz.

24.04.2019 14:00
Bartłomiej Jachowicz, Mateusz Kaczmarek
On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree (M. Equi et al.)
Szukanie dokładnego wzorca w grafie etykietowanym to problem polegający na szukaniu ścieżek w grafie G = (V, E), których etykiety tworzą napis taki sam jak wzorzec P[1…m]. Ten problem można rozwiązać za pomocą algorytmu działającego w kwadratowym czasie O(|E|m). Jednakże w tej pracy, autorzy podają warunkowe ograniczenie dolne na czas działania algorytmu. Przy założeniu Strong Exponential Time Hypothesis (SETH) nie istnieje algorytm działający w czasie O(m |E|1-e) lub  O(|E| m1-e) dla dowolnej stałej e > 0.
17.04.2019 16:15
10.04.2019 16:15
Tomasz Krawczyk
Informatyka Teoretyczna
Testing isomorphism of circular-arc graphs - Hsu's approach revisited
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in a circular-arc graph and can be seen as its canonical representations; in particular, every intersection model can be easily transformed into a normalized one.

Our work adapts and appropriately extends the previous work on similar topic done by Hsu [SIAM J. Comput. 24(3), 411--439, (1995)]. In his work Hsu developed decomposition trees representing the structure of all normalized models of circular-arc graphs. However, due to the counterexample given in [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] his decomposition trees can not be used by the algorithm testing isomorphism of circular-arc graphs.
17.04.2019 14:00
Rafał Kaszuba, Michał Zwonek
A simpler implementation and analysis of Chazelle’s Soft Heaps (H. Kaplan, U. Zwick)
W 2000 roku Chazelle wymyślił nową strukturę danych:  aproksymacyjne priorytetowe kolejki złączalne (Soft Heaps) i użył jej aby uzyskać najszybszy znany deterministyczny algorytm oparty na porównaniach do obliczenia minimalnego drzewa rozpinającego, jak również nowe algorytmy do znajdowania k-tej najmniejszej liczby na liście i przybliżonego sortowania. Jeśli wstawimy do kolekcji miękkich kopców n elementów to co najwyżej εn ze wszystkich elementów będących aktualnie w kopcach dla danego parametru ε może być uszkodzonych, to znaczy ich klucze zostały sztucznie podwyższone. Dzięki pozwoleniu na uszkodzenia każda operacja na miękkim kopcu jest wykonywana w O(log 1/ε) amortyzowanym czasie. Chazelle uzyskał miękkie kopce  przy pomocy kopców dwumianowych, gdzie każda kolejka priorytetowa to kolekcja drzew dwumianowych. W tej pracy autorzy opisują prostszą i bardziej bezpośrednią implementację miękkich kopców, gdzie każda kolejka priorytetowa jest złożona z kolekcji standardowych drzew binarnych. Ta implementacja ma przewagę nad wcześniejszą, bo nie trzeba wykonywać operacji sprzątania, której używał Chazelle w swojej. W pracy przedstawiona jest również zwięzła analiza amortyzowana nowej implementacji.
17.04.2019 12:14
Dawid Tracz
Podstawy Informatyki
Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables by Iovka Boneva, Joachim Niehren, and Momar Sakho
We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on Xml streams with references.
11.04.2019 17:00
Filip Bartodziej
Optymalizacja Kombinatoryczna
Turán’s graph theorem

We’ll cover the Turan theorem from 1941, which provides a restriction on the number of edges in a graph that doesn’t contain an induced k-clique, depending on parameter k.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

11.04.2019 16:15
Mateusz Pabian
Optymalizacja Kombinatoryczna
Gaming is a hard job, but someone has to do it!

General schemes relating the computational complex-ity of a video game to the presence of certain common elements or mechan-ics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Proofs of complexity of several video games, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft.

Giovanni Viglietta. Gaming is a hard job, but someone has to do it! arXiv. 2013.

10.04.2019 12:14
Jan Derbisz
Podstawy Informatyki
What Percentage of Programs Halt? by Laurent Laurent Bienvenu, Damien Desfontaines and Alexander Shen
Fix an optimal Turing machine U and for each n consider the ratio \rho^U_n of the number of halting programs of length at most n by the total number of such programs. Does this quantity have a limit value? In this paper, we show that it is not the case, and further characterise the reals which can be the limsup of such a sequence \rho^U_n . We also study, for a given optimal machine U, how hard it is to approximate the domain of U from the point of view of coarse and generic computability.
04.04.2019 17:00
Marcin Briański
Optymalizacja Kombinatoryczna
A short story of graphs that count

In 1978 Thomason provided a simple, constructive proof of Smith’s theorem; in particular this proof provides a simple algorithm enables one to find a second Hamiltonian cycle whenever one is given a cubic graph and a Hamiltonian cycle in it. For a couple of years, the runtime of the algorithm remained unknown, with worst known cases being cubic (in the number of vertices), however in 1999 Krawczyk found an example of a graph family, such that Thomason’s algorithm takes time Ω(2n/8) where is the number of vertices in the input graph from the family.

In this talk, I will present a family of cubic, planar, and 3-connected graphs, such that Thomason’s algorithm takes time Θ(1.1812n) on the graphs in this family. This scaling is currently the best known.

04.04.2019 16:15
Mateusz Tokarz
Optymalizacja Kombinatoryczna
The Slope Problem
28.03.2019 17:00
Vladyslav Hlembotskyi
Optymalizacja Kombinatoryczna
The Angel of power 2 wins

Let's consider the following game: we have two players (they are called the angel and the devil) and an infinite chessboard. The angel is located in some cell on the board. Players make moves alternatively. The devil chooses any cell that is not occupied by the angle and blocks it. The angel can jump to any other cell which is at distance at most p (p is fixed) from its present location and is not blocked. The devil wins if the angel cannot jump to any other cell. The angel wins if it can avoid being captured forever. We will show that the angel of power 2 has a winning strategy.

András Máthé. The Angel of power 2 wins. Combinatorics, Probability and Computing 16 (2007), no. 3, 363–374.

28.03.2019 16:15
Katarzyna Bułat
Optymalizacja Kombinatoryczna
Distributed tracing

The presentation will cover the topic of distributed tracing, which is an important issue in the field of distributed systems. Services are nowadays implemented as complex networks of related sub-systems and it is often hard to determine the source of performance problem in such complex structures. We will take a look at Dapper, a large-scale distributed systems tracing infrastructure, and discuss the challenges its designers had to face, as well as the opportunities the tool gives to programmers. We will discuss the core goals of effective instrumentation, analyze the problem of handling huge amount of tracing data and focus on security concerns.

21.03.2019 16:15
Adrian Siwiec
Optymalizacja Kombinatoryczna
Online Maximum Matching with Recourse

Online maximum matching problem has a recourse of k, when the decision whether to accept an edge to a matching can be changed k times, where k is typically a small constant. First, we consider the model in which arriving edge never disapears. We show that greedy algorithm has competitive ratio of 3/2 for even k and 2 for odd k. Then we show an improvement for typical values of k and proceed to show a lower bound of 1+1/(k-1). Later, we discuss a model where edges can appear and disappear at any time and show generalized algorithms.

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. arXiv. 2018.

20.03.2019 12:14
Rafał Byczek
Podstawy Informatyki
Improving the Upper Bound on the Length of the Shortest Reset Words by Marek Szykula
We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than 114n^3 / 685+O(n^2). The Cerny conjecture states that (n−1)^2 is an upper bound. So far, the best general upper bound was (n^3−n)/6−1 obtained by J.-E. Pin and P. Frankl in 1982. Despite a number of efforts, it remained unchanged for about 35 years.
To obtain the new upper bound we utilize avoiding words. A word is avoiding for a state q if after reading the word the automaton cannot be in q. We obtain upper bounds on the length of the shortest avoiding words, and using the approach of Trahtman from 2011 combined with the well-known Frankl theorem from 1982, we improve the general upper bound on the length of the shortest reset words. For all the bounds, there exist polynomial algorithms finding a word of length not exceeding the bound.
14.03.2019 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Open problem session

At the seminar were presented some interesting open problems in the field of graph theory.

13.03.2019 14:15
Kornel Dulęba, Jan Mełech
A Randomized Maximum-Flow Algorithm (Cheriyan & Hagerup)

Praca przedstawia randomizowany algorytm obliczający maksymalny przepływ. Dla sieci przepływowej o n wierzchołkach i m krawędziach, czas wykonania jest O(nm + n2(log n)2) z prawdpodobieństwem co najmniej 1 - 2-sqrt(nm). Algorytm jest zawsze poprawny i w najgorszym przypadku działa w czasie O(nm log n). Czynnik randomizujący składa się tylko z zastosowania losowych permutacji do list sąsiedztwa wierzchołków na początku algorytmu.

13.03.2019 12:14
Vladyslav Hlembotskyi
Podstawy Informatyki
Upper Bounds for Standardizations and an Application by Hongwei Xi
We present a new proof for the standardization theorem in lambda-calculus, which is largely built upon a structural induction on lambda-terms. We then extract some bounds for the number of beta-reduction steps in the standard beta-reduction sequence obtained from transforming a given beta-reduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of beta-reduction sequences from any given simply typed A
07.03.2019 16:15
Kamil Kropiewnicki
Optymalizacja Kombinatoryczna
Identities versus bijections

In 1740 Leonhard Euler began to work on counting partitions. It resulted in two fundamental papers in the field. Integer partitions have been an active field of study ever since, tackled by many including Srinivasa Ramanujan, Paul Erdős and Donald Knuth. We present a few beautiful proofs of identities using only basic generating functions and simple bijections.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

06.03.2019 16:15
Zoltán Lóránt Nagy
Eötvös University & Alfréd Rényi Institute of Mathematics
Informatyka Teoretyczna
Triangles in line arrangements

A widely investigated subject in combinatorial geometry, originating from Erdős, is the following: given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances, e.g., determine the maximum number of unit distances, the maximum number of minimum/maximum distances, the minimum number of distinct distances? This has been generalized in many directions by taking point sets in a certain (not necessarily Euclidean) metric space and studying the distribution of certain configurations — and a whole theory emerged.

In this talk I propose the following problem variant: consider planar line arrangements of n lines, and determine the maximum number of unit/maximum/minimum area determined by these lines. We prove that the order of magnitude for the maximum occurrence of unit area lies between n2 and n2+1/4. This result is strongly connected to both additive combinatorial results and Szemerédi-Trotter type results. Next we show a tight bound for the maximum number of minimum area triangles. Finally we discuss a graph theoretic approach for the maximum number of maximum area triangles and present a recursive lower bound.

Joint work with Gábor Damásdi, Leo Martínez-Sandoval and Dániel T. Nagy.

06.03.2019 12:14
Jan Derbisz, Pola Kyzioł, Krzysztof Maziarz, Jakub Nowak, Grzegorz Juzrdziński
Podstawy Informatyki
Prezentacje prac magisterskich

Jan Derbisz, Promotor: dr hab. Tomasz Krawczyk
Wykorzystanie matroidów w algorytmach.

Pola Kyzioł, Promotor: dr hab. Tomasz Krawczyk
Cut & Count technique and its application to NP.-compelete graph problems that require connectivity

Krzysztof Maziarz, Promotor: prof. dr hab. Jacek Tabor
Evolutionary-Neural Hybrid Agents for Architecture Search

Jakub Nowak, Promotor: prof. dr hab. Jacek Tabor
Application of functional image representation

Grzegorz Jurdziński, Promotor: dr Piotr Micek
Głębokie sieci neuronowe w rozpoznawaniu mowy

27.02.2019 16:15
Michał Wrona
Informatyka Teoretyczna
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by first-order expansions of countably infinite homogeneous graphs, that are, the structures first-order-definable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H.

Our main result is that structures under consideration have relational width exactly (2,L) where L is the maximal size of a forbidden subgraph in S, but not smaller than 3. It implies, in particular, that the CSP parametrized by such structures may be solved in time O(nm) where n is the number of variables and m is the maximum of L and the arities of relations in the signature, while strict width l ensures time O(nl+1). Furthermore, since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures, in which case, if finite, relational width is always at most (2,3). 

Finally, we show that certain maximally tractable constraint languages with a first-order definition in a countably infinite homogeneous graph whose CSPs are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, providing an alternative algorithm for already studied problems.

26.02.2019 16:15
Marcin Briański
Algorytmy Randomizowane i Aproksymacyjne
Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz)
24.01.2019 16:15
Rafał Burczyński
Optymalizacja Kombinatoryczna
Basic properties of 3CCP graphs

We will introduce a class of graphs called 3CCP, which contains graphs that are 3-connected, cubic (3-regular) and planar. It was shown by Tarjan that finding Hamiltonian cycle in a graph assuming these properties remains NP-complete - we will show the reduction from 3-SAT problem. After that we will present Smith's theorem about parity of number of Hamiltonian cycles containing given edge in cubic graphs and show elegant constructive proof using Thomason's lollipop method. After that we will show a class of graphs for which previous algorithm for finding second Hamiltonian cycle takes exponential number of steps.

24.01.2019 14:00
Jan Derbisz, Franciszek Stokowacki
An Equivalence Class for Orthogonal Vectors (L.Chen, R.Williams)
Problem sprawdzania, czy pośród n wektorów istnieje para wektorów ortogonalnych umiemy łatwo rozwiązać w czasie O(n2 log n), jednak nie jest znany algorytm szybszy niż n2. Autorzy pracy dowodzą, że istnienie algorytmu podkwadratowego jest równoważne istnieniu takich algorytmów dla kilku innych problemów, między innymi Apx-Min-IP - znajdowania pary wektorów będących k-aproksymacją maksymalnego iloczynu skalarnego oraz Approximate Bichrom.-ℓp-Closest-Pair - problemu znajdowania aproksymowanej najbliższej dwukolorowej pary punktów. Powyższe równoważności są zachowane w sytuacji, w której zamiast odpowiadać offline mamy strukturę danych i odpowiadamy na zapytania online. Dodatkowo w pracy przedstawione są nowe algorytmy aproksymowane dla Apx-Min-IP oraz rozwiązywania pewnych instancji MAX-SAT.
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.

23.01.2019 12:14

Podstawy Informatyki
17.01.2019 16:15
Adrian Siwiec
Optymalizacja Kombinatoryczna
List coloring of Latin Squares

For each cell (i, j) of NxN square there is given a list C(i, j) of N colors. Can we choose a color for each cell in such a way that colors in each row and each column are distinct?

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

17.01.2019 14:00
Katarzyna Bułat, Kamil Rajtar
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 16:15
Kamil Kropiewnicki
Optymalizacja Kombinatoryczna
Shuffling cards

What do the birthday paradox, the coupon collector problem and shuffling cards have in common? What does it mean for a deck of cards to be "random" or "close to random"? How long does one have to shuffle a deck of cards until it is random? In practical use cases, the question is not about the asymptote - it is about the exact numbers.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

10.01.2019 14:00
Bartłomiej Jachowicz, Mateusz Kaczmarek
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 16:15
Kamil Rajtar
Optymalizacja Kombinatoryczna
Communication without errors

Main aim of the lecture is the answer for Claude Shannon's question from 1956: "Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?"

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

03.01.2019 14:00
Rafał Kaszuba, Krzysztof Zysiak
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.

20.12.2018 16:15
Filip Bartodziej
Optymalizacja Kombinatoryczna
Cayley’s formula for the number of trees & How to guard a museum

First, several proofs for the number of labeled trees, each using different approach (bijection, linear algebra, recursion, double counting) will be presented. Second part of the seminar will introduce an interesting graph problem first raised by Victor Klee in 1973. This problem can be represented as placing guards in a museum to guard it properly - that is area of the museum must be completely covered by the field of view of the guards.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

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 17:00
Franciszek Stokowacki
Optymalizacja Kombinatoryczna
An Approximate Restatement of the Four-Color Theorem

Four color theorem was proven in 1976 with extensive computer help. Since then there is interest in finding a simpler proof that uses no computer computation. I will present relation between Four Color Theorem and edge 3-coloring of planar, cubic graphs without bridges, and a new result proving that the existence of approximate coloring (with the fourth color used ‘rarely’) is enough to imply Four Color Theorem.

Atish Das Sarma, Amita S. Gajewar, Richard Lipton, Danupon Nanongkai. An approximate restatement of the four-color theorem. Journal of Graph Algorithms and Applications 17(5), pages 567–573, 2013.

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
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
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
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
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
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
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 14:00
Tomasz Zieliński, Michał Zwonek
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
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.