Seminaria
01.01.2021 16:15 Grzegorz Gutowski 
Informatyka Teoretyczna TBA  Gutowski 
01.01.2021 16:15 Bartosz Walczak 
Informatyka Teoretyczna TBA  Walczak 
01.01.2021 16:15 Paweł Idziak 
Informatyka Teoretyczna Modular circuits satisfiability of intermediate complexity 
In our paper [LICS'18] a generalization of Boolean circuits to arbitrary finite algebras was introduced and applied to sketch P versus NPcomplete borderline for circuits satisfiability over algebras from congruence modular varieties. However nilpotent but not supernilpotent algebras have not been put on any side of this borderline. This paper provides a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce Boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general. Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy was shown by Bulatov and Zhuk. Joint work with Piotr Kawałek and Jacek Krzaczkowski 
01.01.2021 16:15 Krzysztof Turowski 
Informatyka Teoretyczna Degree Distribution of Dynamic Graphs Generated by a DuplicationDivergence Models 
We analyze the structure of dynamic graphs generated from duplication models in which a new vertex selects an existing vertex and copies some of its neighbors and then we add some random divergence. We analyze various graph parameters like mean degree, number of open triangles, number of triangles, number of vertices of degree k or maximum degree in a graph generated from such models. We provide asymptotic analysis of expected values and tail behavior of these parameters. We also point to further extensions of this approach towards computing symmetries in these graphs and algorithms for graph compression.

Poprzednie referaty
10.06.2020 17:00 Bartosz Wodziński 
Optymalizacja Kombinatoryczna On the unique games conjecture 
For many hard problems, instead of solving them directly, we need good approximation algorithms. Apart from good their time complexity and decent approximation factor guarantee, we would like to know whether they achieve the best possible approximation ratio (assuming P ≠ NP) possible. Unfortunately, for many NPcomplete problems, there is a huge gap between bestknown approximation ratio and the ratio that is proved to be unachievable in polynomial time. For instance, for Vertex Cover problem, we don't know any algorithm having a better ratio than 2, and it has been proved in 2005 that it is impossible to get a better ratio than ~1.36. As an attempt to fill in this gap, in 2002, the socalled Unique Games Conjecture was formulated by Khot. It states that having a (1𝜀)satisfiable instance of Unique Label Cover problem, it is NPhard to find a solution satisfying even epsilon fraction of constraints. Assuming it, we are able to prove many tight inapproximability results, for example, it implies that GoemansWilliamson Algorithm for MaxCut problem achieves the best possible approximation rate. It also follows that we cannot get any better ratio than 2 in the case of Vertex Cover problem. The Unique Games Conjecture is an unusual open problem since the academic world is about evenly divided on whether it is true or not. During the seminar, I will cover this conjecture in more details giving more examples of its influence and presenting recent progress in order to prove it.
(the seminar will only be online) 
10.06.2020 16:15 Gabriela Czarska 
Optymalizacja Kombinatoryczna The Lonely Runner Conjecture 
Abstract. Suppose that k runners having different constant speeds run laps on a circular track of unit length. The Lonely Runner Conjecture states that, sooner or later, any given runner will be at distance at least 1/k from all the other runners. We prove that with probability tending to one, a much stronger statement holds for random sets in which the bound 1/k is replaced by 1/2 − ε. The proof uses Fourier analytic methods. We also point out some consequences of our result for colouring of random integer distance graphs. (the seminar will only be online) 
10.06.2020 12:15 Wojciech Grabis 
Podstawy Informatyki Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup 
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of L_gen to be the minimal size of all finite deterministic automata of genus g(L) computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size Lgen can grow at least exponentially in size L. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genusbased hierarchies of regular languages and in particular, we show a new family of regular languages on a twoletter alphabet having arbitrary high genus. 
10.06.2020 12:15 Wojciech Grabis 
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup 
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of Lgen to be the minimal size of all finite deterministic automata of genus g(L) computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size Lgen can grow at least exponentially in size L. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genusbased hierarchies of regular languages and in particular, we show a new family of regular languages on a twoletter alphabet having arbitrary high genus. 
10.06.2020 12:15 Wojciech Grabis 
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup 
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of Lgen to be the minimal size of all finite deterministic automata of genus g(L) computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size Lgen can grow at least exponentially in size L. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genusbased hierarchies of regular languages and in particular, we show a new family of regular languages on a twoletter alphabet having arbitrary high genus. 
10.06.2020 12:15 Wojciech Grabis 
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup 
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of L_gen to be the minimal size of all finite deterministic automata of genus g(L) computing L. We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size L_gen can grow at least exponentially in size L. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genusbased hierarchies of regular languages and in particular, we show a new family of regular languages on a twoletter alphabet having arbitrary high genus. 
04.06.2020 17:00 Paweł Mader 
Optymalizacja Kombinatoryczna Oblivious routing on 2d grid 
Oblivious routing is a routing problem, in which a packet path is selected independently from path choices of other packets. One of the open problems is to find networks for which there exists an oblivious routing algorithm, which allows simultaneously optimizing stretch and congestion of the network. We are presenting an algorithm for oblivious routing on 2dgrid, which is O(log n) approximation for congestion and Θ(1) approximation of stretch. (the seminar will only be online) 
04.06.2020 16:15 Raja L'hamri Mohammed V University 
Optymalizacja Kombinatoryczna Examples of codes from zerodivisor graphs 
In 2013, Dankelmann, Key, and Rodrigues introduced and investigated codes from incidence matrices of a graph. Several authors have been developed their study to several context. In this talk, we present some properties of codes associated with zero divisor graphs. Recall, the zero divisor graph of R denoted by Γ(R), is the simple graph associated with R whose set of vertices consists of all nonzero zerodivisors of R such that two distinct vertices x and y are joined by an edge if xy = 0. This is joint work with K. Abdelmoumen, D. Bennis, and F. Taraza.
(the seminar will only be online) 
03.06.2020 12:15 Ruslan Yevdokymov 
Podstawy Informatyki Learnability can be undecidable by Shai BenDavid, Pavel Hrubes, Shay Moran, Amir Shpilka and Amir Yehudayoff 
The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression. 
28.05.2020 17:00 Michał Stobierski 
Optymalizacja Kombinatoryczna The 123 Conjecture 
We all know how important mathematical theorems are in general. Less obvious is the fact that theorems in one area like algebra or number theory could have a significant impact on another. In our case, these will be combinatorial problems. In this presentation, We will go through a few simple graph coloring questions (based on the original 123 Conjecture), which unfortunately don't have simple solutions at all and we'll classify them. Moreover, thanks to Combinatorial Nullstellensatz and some greedy techniques, we will be able to prove some weaker versions of our original claims. And finally, we will see how one simple question, through a chain of small modifications, can lead us to completely different problems. (the seminar will only be online) 
28.05.2020 16:15 Rafał Byczek 
Optymalizacja Kombinatoryczna Wegner’s conjecture  colouring the square of a planar graph 
The square G^{2} of a graph G is the graph with the same vertex set in which two vertices are joined by an edge if their distance in G is at most two. The chromatic number of the square of a graph G is between D + 1 and D^{2 }+ 1, where D is the maximum degree of G. Equivalently, the square coloring of a graph is to color the vertices of a graph at distance at most 2 with different colors. In 1977, Gerd Wegner proved that the square of cubic planar graphs is 8colorable. He conjectured that his bound can be improved  the chromatic number of G^{2} is at most 7, if D = 3, at most D + 5, if 4 ≤ D ≤ 7, and [3D / 2] + 1, otherwise. Wegner also gave some examples to illustrate that these upper bounds can be obtained. C. Thomassen (2006) proved the conjecture is true for planar graphs with D = 3. The conjecture is still open for planar graphs with D ≥ 4. However several upper bounds in terms of maximum degree D have been proved as follows. In 1993, Jonas proved that χ(G^{2}) ≤ 9D19, for planar graphs with D ≥ 5. Agnarsson and Halldorson showed that for every planar graph G with maximum degree D ≥ 749, χ(G^{2}) ≤ [9D / 5] + 2. Van den Heuvel and McGuinness (2003) showed that χ(G^{2}) ≤ 2D + 25, Bordin (2002) proved that χ(G^{2}) ≤ [9D / 5] + 1, if D ≥ 47, and Molloy and Salavatipour (2005) proved χ(G^{2}) ≤ [5D / 3] + 78, moreover, χ(G^{2}) ≤ [5D / 3] + 25 if D ≥ 241. Moreover, conjecture is confirmed in the case of outerplanar graphs and graphs without K_{4} minor. The aim of the seminar will be to present the main facts about Wegner’s conjecture and main techniques and ideas which were used to prove some upper bounds. The presentation will be based on my master thesis. (the seminar will only be online) 
27.05.2020 12:00 Szymaon Kapała 
Podstawy Informatyki Searching for shortest and least programs by Cristian Caludea, Sanjay Jain, Wolfgang Merkle and Frank Stephan 
The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U(p) =x and p is a shortest string with this property. Neither the plain nor the prefixfree version of Kolmogorov complexity are recursive but for both versions it is wellknown that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f(x) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the lengthlexicographically least program. The main results which hold in the plain as well as in the prefixfree setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefixfree frameworks are obtained by considering effective sequences I_1, I_2, ...of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I_n to its least code. Such coding functions do not exist in the prefixfree setting but exist in the plain setting in case the sets I_n are not too small. 
21.05.2020 16:15 Wojtek Grabis 
Optymalizacja Kombinatoryczna Algorithms for Destructive Shift Bribery. 
Destructive Shift Bribery is a problem in which we are given an election with a set of candidates and a set of voters, a budget , a despised candidate and price for shifting the despised candidate in the voters rankings. Our objective is to ensure that selected candidate cannot win the election. We're going to study the complexity of this problem under diffrent election methods.
(the seminar will only be online) 
20.05.2020 12:15 Piotr Mikołajczyk 
Podstawy Informatyki Lambda Calculus and Probabilistic Computation by Claudia Faggian and Simona Ronchi della Rocca 
We introduce two extensions of the lambda calculus with a probabilistic choice operators, modeling respectively callbyvalue and callbyname probabilistic computation. We prove that both enjoys confluence and standardization, in an extended way: we revisit these two fundamental notions to take into account the asymptotic behaviour of terms. The common root of the two calculi is a further calculus based on Linear Logic ! which allows us to develop a unified, modular approach. 
14.05.2020 17:00 Jan Mełech 
Optymalizacja Kombinatoryczna Upper Bounds for the domination numbers of graphs 
Sharareh Alipour and Amir Jafari showed various upper bounds for minimal cardinality of (a,b)dominating set. For positive integers a and b, a subset S ⊆ V(G) is an (a,b)dominating set if every vertex v ∈ S is adjacent to at least a vertices inside S and every vertex v ∈ V\S is adjacent to at least b vertices inside S. To achieve upper bounds, the authors used Turan's Theorem and Lovasz Local Lemma. These tools allowed them to obtain wellknown bounds in a simpler way or new improved bounds in some special cases, including regular graphs.
(the seminar will only be online) 
14.05.2020 16:15 Szymon Kapała 
Optymalizacja Kombinatoryczna Goldbach conjectures (weak and strong). 
(the seminar will only be online) 
13.05.2020 12:15 Przemysław Simajchel 
Podstawy Informatyki Dance of the Starlings by Henk Barendregt, Jorg Endrullis, Jan Klop and Johannes Waldmann 
In this birdwatching paper our binoculars are focused upon a particular bird from Smullyan's enchanted forest of combinatory birds, to wit the Starling. In the feathers of lambda calculus this bird has the plumage \abc:ac(bc). This term is usually named S, reminiscent of its inventor Schonfinkel and also the combinatory ornithologist Smullyan. The combinator S is important for a variety of reasons. First, it is part of the \{ S, K\} basis for Combinatory Logic (CL). Second, there are several interesting questions and observations around S, mostly referring to termination and word problems. Our paper collects known facts, but poses in addition several new questions. For some of these we provide solutions, but several tough open questions remain. 
07.05.2020 16:15 Michał Zwonek 
Optymalizacja Kombinatoryczna 3flow conjecture 
3flowconjecture Grötzsch proved that every triangle free (and loopless) planar graph is 3colorable. By flow/coloring duality, this is equivalent to the statement that every 4edgeconnected planar graph has a nowherezero 3flow. The 3flow conjecture asserts that this is still true without the assumption of planarity. Jaeger proved that 4edgeconnected graphs have nowherezero 4flows. The following weak version of the 3flow conjecture used to remain open until 2010, but the original 3flow conjecture remains wide open. C̶o̶n̶j̶e̶c̶t̶u̶r̶e̶ (The weak 3flow conjecture (Jaeger)) These problems and the surrounding results will be presented during the seminar.
(the seminar will only be online) 
06.05.2020 12:15 Bartłomiej Puget 
Podstawy Informatyki Evidence Normalization in System FC by Dimitrios Vytiniotis and Simon Peyton Jones 
System FC is an explicitly typed language that serves as the target language for Haskell source programs. System FC is based on System F with the addition of erasable but explicit type equality proof witnesses. Equality proof witnesses are generated from type inference performed on source Haskell programs. Such witnesses may be very large objects, which causes performance degradation in later stages of compilation, and makes it hard to debug the results of type inference and subsequent program transformations. In this paper, we present an equality proof simplification algorithm, implemented in GHC, which greatly reduces the size of the target System FC programs. 
30.04.2020 17:00 Mateusz Kaczmarek 
Optymalizacja Kombinatoryczna χboundedness 
If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? To answer that question Paul Seymour and Alex Scott took a closer look at recent progress in this field in their χboundedness survey. Based on their work I will present some results on forests and holes and few open problems like GyárfásSumner conjecture or χboundedness connection to ErdősHajnal conjecture.
(the seminar will only be online) 
30.04.2020 16:15 Kornel Dulęba 
Optymalizacja Kombinatoryczna Odd Perfect numbers 
A number is perfect if it is equal to the sum of its divisors. So far only even perfect numbers have been found. For example, it was proven that squares of Mersenne’s numbers are perfect. However, no one has been able to prove that odd perfect numbers don’t exist. I’m going to start by presenting a summary of known facts about odd prime numbers. Then I’ll prove that an odd perfect number with at least eight distinct prime factors has to be divisible by 5.
(the seminar will only be online) 
29.04.2020 12:15 Jakub Dyczek 
Podstawy Informatyki On probabilistic term rewriting by Martin Avanzinia,Ugo Dal Lago and Akihisa Yamadac 
We study the termination problem for probabilistic term rewrite systems. We prove that the interpretation method is sound and complete for a strengthening of positive almost sure termination, when abstract reduction systems and term rewrite systems are considered. Two instances of the interpretation method polynomial and matrix interpretations are analyzed and shown to capture interesting and nontrivial examples when automated. We capture probabilistic computation in a novel way by means of multidistribution reduction sequences, thus accounting for both the nondeterminism in the choice of the redex and the probabilism intrinsic in firing each rule. 
23.04.2020 17:00 Bartłomiej Jachowicz 
Optymalizacja Kombinatoryczna Lonely runner conjecture 
One of number theory open problem is the Lonely Runner Conjecture. It is interesting for several reasons. First the conjecture is relatively intuitive to grasp and easy to state. This conjecture can be find in two different contexts: as a problem in Diophantine’s approximation and as a geometric view obstruction problem. What is more, the difficulty of proving the Lonely Runner Conjecture may seem to increase exponentially with the number of runners. I present statement of the conjecture and known partial results.
(the seminar will only be online) 
23.04.2020 16:15 Filip Bartodziej 
Optymalizacja Kombinatoryczna Meyniel’s conjecture on the cop number 
A cops and robbers problem determines if the number of cops is sufficient to always catch a robber in a game with defined rules played on an undirected graph. Cop number of a graph is the minimal number of cops necessary for cops to win in that game on the specific graph. Mayniel’s conjuncture remains an open problem and states that cop number for graphs of order n is sqrt(n). I’ll present a survey of results achieved that are related to this conjecture.
(the seminar will only be online) 
22.04.2020 12:15 Jan Kościsz 
Podstawy Informatyki Fast Synchronization of Random Automata by Cyril Nicaud 
A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerný conjectured in 1964 that if a nstate deterministic automaton has a synchronizing word, then it has a synchronizing word of length at most (n − 1)^2. Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization: he proved that, for the uniform distribution on deterministic automata with n states, an automaton admits a synchronizing word with high probability. In this article, we are interested in the typical length of the smallest synchronizing word, when such a word exists: we prove that a random automaton admits a synchronizing word of length O(n log^3 n) with high probability. As a consequence, this proves that most automata satisfy the Cerný conjecture. 
16.04.2020 17:00 Mateusz Pabian 
Optymalizacja Kombinatoryczna Synchronizing Automata and the Černý Conjecture 
I present many results and finally open problem related to synchronizing automata and synchronizing word sends any state of the DFA to one and the same state. This leads to the some natural problems such as: how can we restore control over such a device if we don't know its current state but can observe outputs produced by the device under various actions? I prove some uperbounds for length of this kind of word and in particular I will make a statement of Cerny conjecture.
(the seminar will only be online) 
16.04.2020 16:15 Adrian Siwiec 
Optymalizacja Kombinatoryczna Online Computation with Untrusted Advice 
The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. We study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust and perform well even when the advice is generated in a malicious, adversarial manner.To this end, we focus on wellstudied online problems such as ski rental, online bidding, bin packing, and list update.
(the seminar will only be online) 
15.04.2020 12:15 Magdalena Proszewska 
Podstawy Informatyki Singular value automata and approximate minimization by Borja Balle, Prakash Panangaden and Doina Precup 
The present paper uses spectral theory of linear operators to construct approximately minimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for the singular value decomposition (SVD) decomposition of finiterank infinite Hankel matrices based on their representation in terms of weighted automata, (ii) a new canonical form for weighted automata arising from the SVD of its corresponding Hankelmatrix, and (iii) an algorithm to construct approximate minimizations of given weighted automata by truncating the canonical form. We give bounds on the quality of our approximation. 
09.04.2020 17:00 Wojciech Buczek 
Optymalizacja Kombinatoryczna Seymour's Second Neighbourhood Conjecture 
Seymour's Second Neighbourhood Conjecture tells us, that any oriented graph has a vertex whose outdegree is at most its second outdegree, which is also known as Second neighborhood problem. Intuitively, it suggests that in a social network described by such a graph, someone will have at least as many friendsoffriends as friends. We will say about ChenShenYuster prove, that for any digraph D, there exists a vertex v such that N^{++}(v)≥γN^{+}(v), where γ=0.67815. We will consider graphs, in which we know, that such vertex exists. We will also say about unsuccessful attempts at proving this conjecture.
(the seminar will only be online) 
09.04.2020 16:15 Mikołaj Twaróg 
Optymalizacja Kombinatoryczna Collatz conjecture 
The Collatz conjecture, also known as 3n + 1 conjecture considers a function, which returns n/2 if n is even and 3n + 1 if n is odd. The conjecture states that for every n we can repeatedly apply this function to eventually reach 1. I will talk about different approaches to proving this conjecture. (the seminar will only be online) 
08.04.2020 12:15 Jacek Kurek 
Podstawy Informatyki Complexity of translations from resolution to sequent calculus by GISELLE REIS and BRUNO PALEO 
Resolution and sequent calculus are two wellknown formal proof systems. Their differences make them suitable for distinct tasks. Resolution and its variants are very efficient for automated reasoning and are in fact the theoretical basis of many theorem provers. However, being intentionally machine oriented, the resolution calculus is not as natural for human beings and the input problem needs to be preprocessed to clause normal form. Sequent calculus, on the other hand, is a modular formalism that is useful for analysing metaproperties of various logics and is, therefore, popular among proof theorists. The input problem does not need to be preprocessed, and proofs are more detailed. However, proofs also tend to be larger and more verbose. When the worlds of proof theory and automated theorem proving meet, translations between resolution and sequent calculus are often necessary. In this paper, we compare three translation methods and analyse their complexity. 
02.04.2020 17:00 Adam Pardyl 
Optymalizacja Kombinatoryczna Undirected edge geography 
The game of edge geography is played by two players who alternately move a token on a graph from one vertex to an adjacent vertex, erasing the edge in between. The player who first has no legal move loses the game. We analyze the space complexity of the decision problem of determining whether a start position in this game is a win for the first player. We also show a polynomial time algorithm for finding winning moves for bipartite graphs.
(the seminar will only be online) 
02.04.2020 16:15 Piotr Mikołajczyk 
Optymalizacja Kombinatoryczna ARRIVAL game 
Consider a directed graph such that every vertex has at most 2 outgoing edges  one of them is labeled as 'open' (we can traverse it) and the second one is labeled as 'closed' (we cannot traverse it). Every time we go somewhere from the vertex v, labels at its two edges are swapped, so the next time we visit v, we will take another direction. Given designated two vertices: origin and destination, we need to decide, whether eventually we will reach destination starting in the origin. This problem lies in both NP and coNP, but it is still an open question whether it belongs to P.
(the seminar will only be online) 
01.04.2020 12:15 Rafał Byczek 
Podstawy Informatyki Bijection between oriented maps and weighted nonoriented maps by Agnieszka CzyzewskaJankowska and Piotr Śniady 
We consider bicolored maps, i.e. graphs which are drawn on surfaces, and construct a bijection between (i) oriented maps with arbitrary face structure, and (ii) (weighted) nonoriented maps with exactly one face. Above, each non oriented map is counted with a multiplicity which is based on the concept of the orientability generating series and the measure of orientability of a map. This bijection has the remarkable property of preserving the underlying bicolored graph. Our bijection shows equivalence between two explicit formulas for the topdegree of Jack characters, i.e. (suitably normalized) coefficients in the expansion of Jack symmetric functions in the basis of powersum symmetric functions. 
26.03.2020 16:15 Vladyslav Rachek 
Optymalizacja Kombinatoryczna Small weak epsilonnets 
Let P be a set of n points in R^{2}. A point q (not necessarily in P) is called a centerpoint of P if each closed halfplane containing q at least ⌈n/3⌉ points of P, or, equivalently, any convex set that contains more than ^{2}/_{3 }n points of P must also contain q. It is a wellknown fact that a centerpoint always exists and the constant ^{2}/_{3} is the best possible. Can we improve this constant by using, say, two points, or some other small number of points? In the presentation we'll try to answer those questions. Vladyslav Rachek. Small weak epsilonnets. slides. 2020. (the seminar will only be online) 
25.03.2020 12:15 Michał Zwonek 
Podstawy Informatyki FUNCTIONAL PEARL How to find a fake coin by RICHARD BIRD 
The aim of this pearl is to solve the following wellknown problem that appears in many puzzle books, for example Levitin & Levitin (2011) and Bellos (2016), usually for the particular case n=12.

19.03.2020 17:00 Kamil Rajtar 
Optymalizacja Kombinatoryczna How voting can be manipulated during selecting voting places 
During today presentation we will learn how we can use graph theory to proof hardness of general problem of manipulating poll outcome. Based on paper: "Selecting Voting Locations for Fun and Profit" written by Zack Fitzsimmons and Omer Lev. Zack Fitzsimmons, Omer Lev. Selecting Voting Locations for Fun and Profit. arXiv:2003.06879. 2020. (the seminar will only be online) 
19.03.2020 16:15 Mateusz Tokarz 
Optymalizacja Kombinatoryczna The HadwigerNelson problem 
We will focus on HadwigerNelson problem  an open question from geometric graph theory that asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. There are a few interesting theorems related to the problem and results which we will go through. We will focus in particular on the most recent result of Aubrey de Grey who showed that the desired chromatic number is at least 5.
(the seminar will only be online) 
18.03.2020 12:15 Mateusz Tokarz, wyniki własne, kontynuacja 
Podstawy Informatyki The largest fixed point in iterative programs 
We study the smallest ordinal number α such that every Prologue program will reach its greatest fixed point after α downward iterations. Firstly, we show that the continuity of Prologue’s resolution function does not help with this matter. Then, due to the embedding of the recursive functions in Prologue, we get that α is at least ChurchKleene Omega. Using recursive linear order presented in “On the Forms of the Predicates in the Theory of Constructive Ordinals“ (Kleene, 1944) we construct a Prologue’s program requiring at least CK Omega steps to achieve its greatest fixed point. To get the upper bound on α we use clockable ordinals introduced in “Infinite Time Turing Machines” (Joel David Hamkins, Andy Lewis, 1998). 
11.03.2020 12:15 Mateusz Tokarz wyniki własne 
Podstawy Informatyki The largest fixed point in iterative programs 
We study the smallest ordinal number α such that every Prologue program will reach its greatest fixed point after α downward iterations. Firstly, we show that the continuity of Prologue’s resolution function does not help with this matter. Then, due to the embedding of the recursive functions in Prologue, we get that α is at least ChurchKleene Omega. Using recursive linear order presented in “On the Forms of the Predicates in the Theory of Constructive Ordinals“ (Kleene, 1944) we construct a Prologue’s program requiring at least CK Omega steps to achieve its greatest fixed point. To get the upper bound on α we use clockable ordinals introduced in “Infinite Time Turing Machines” (Joel David Hamkins, Andy Lewis, 1998). 
23.01.2020 16:15 Jan Gwinner 
Optymalizacja Kombinatoryczna Spectrally Robust Graph Isomorphism 
In the paper authors consider certain variants of Graph Isomorphism problem. They focus on properties of graph spectra and eigenspaces  namely if Laplacian of one of the graphs is greater or equal to another in Loewner ordering. In the first part of the paper they prove that one of the problems named Spectral Graph Dominance is NPC. The rest of the paper is devoted to an approximation algorithm for special case of the problem called Spectrally Robust Graph Isomorphism. 
22.01.2020 12:15 Weronika Grzybowska i Mateusz Tokarz 
Podstawy Informatyki On two subclasses of Motzkin paths and their relation to ternary trees by Helmut Prodinger, Sarah J. Selkirk and Stephan Wagner 
Two subclasses of Motzkin paths, SMotzkin and TMotzkin paths, are introduced. We provide bijections between SMotzkin paths and ternary trees, SMotzkin paths and noncrossing trees, and TMotzkin paths and ordered pairs of ternary trees. Symbolic equations for both paths, and thus generating functions for the paths, are provided. Using these, various parameters involving the two paths are analyzed. 
16.01.2020 17:00 Gabriela Czarska 
Optymalizacja Kombinatoryczna Driver surge pricing 
Authors study Uber's pricing mechanisms from the perspective of drivers, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. They present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings. Nikhil Garg, Hamid Nazerzadeh. Driver Surge Pricing. arXiv. 2019. 
16.01.2020 16:15 Bartosz Podkanowicz 
Optymalizacja Kombinatoryczna Planar graphs have bounded queuenumber 
The paper presents proof that the queue number of planar graphs is bounded. It also mentions generalizations of the result and other theorems that have similar proofs. 
16.01.2020 14:15 Katarzyna Król, Paweł Mader 
Algorytmika On the Complexity of Lattice Puzzles [Kobayashi et al.] 
Autorzy pracy badają złożoność obliczeniową tradycyjnej łamigłówki zwaną dalej układanką kratową. Celem układanki jest złożenie kraty o wymiarach n×n z 2n płytek z szczelinami. Łamigówka ta jest powszechnie znanym problemem, niemniej jednak do tej pory nie była ona badana przez informatykę teoretyczną. Autorzy pracy pokazują, że naturalne warianty tej układanki redukują się do podklas w klasie złożoności NP. Jedną z takich podklas jest klasa problemu izomorfizmów grafów GI. O ile wiadomo autorom pracy, jest to pierwszy nietrywialny GIzupełny problem scharakteryzowany przez klasyczną łamigłówkę. 
15.01.2020 16:15 Michał Seweryn 
Informatyka Teoretyczna ErdösHajnal properties for powers of sparse graphs 
The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory and algorithmics. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs, a positive real ε and a positive integer d, in any nvertex graph G in the class, there are disjoint vertex subsets A and B with A=Ω(n) and B=Ω(n^{1ε}) such that in the dth power of G, either there is no edge between A and B, or there are all possible edges between A and B.
Joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk 
15.01.2020 12:15 Wojciech Grabis 
Podstawy Informatyki Ant colony optimization theory: A survey by Marco Dorigoa and Christian Blumb 
Research on a new metaheuristic for optimization is often initially focused on proofofconcept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method’s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we reviewsome convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. 
09.01.2020 17:00 Wojtek Grabis 
Optymalizacja Kombinatoryczna Algorithms for Destructive Shift Bribery. 
Destructive Shift Bribery is a problem in which we are given an election with a set of candidates and a set of voters, a budget , a despised candidate and price for shifting the despised candidate in the voters rankings. Our objective is to ensure that selected candidate cannot win the election. We're going to study the complexity of this problem under diffrent election methods. Andrzej Kaczmarczyk, Piotr Faliszewski. Algorithms for Destructive Shift Bribery. arXiv. 2018. 
09.01.2020 16:15 Dominik Gryboś 
Optymalizacja Kombinatoryczna Imperfect Forward Secrecy: How DiffieHellman Fails in Practice 
The paper shows that the DiffieHellman protocol is not as secure as we thought. The authors present the Logjam attack, which consists in quickly calculating discrete logarithms based on previously performed calculations. This can be done because many websites use the same prime numbers in the message encryption process. 
08.01.2020 12:15 Piotr Gaiński 
Podstawy Informatyki How Similar Are Two Elections by Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Stanisław Szufa and Nimrod Talmon 
We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as dISOMORPHISM DISTANCE (dID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomialtime solvable, and that the dISOMORPHISM DISTANCE problems generalize various classic rankaggregation methods (e.g., those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice. 
19.12.2019 17:00 Kamil Kropiewnicki 
Optymalizacja Kombinatoryczna Impossibility of Distributed Consensus with One Faulty Proces 
he consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem. Authors of the paper were awarded a Dijkstra Prize for this work  given to the most influential papers in distributed computing. 
19.12.2019 16:15 Filip Bartodziej 
Optymalizacja Kombinatoryczna How to eat 4/9 of a pizza 
Unevenly cut pizza is a frustrating occurrence. How can we then make sure that a friend is not trying to reduce our portion of the delicious meal? We will present a strategy which guarantees that one will leave the table satisfied, assuming that they started eating first. Kolja Knauer, Piotr Micek, Torsten Ueckerdt. How to eat 4/9 of a pizza. arXiv. 2008. 
18.12.2019 12:15 Bartosz Podkanowicz 
Podstawy Informatyki Riordan arrays and combinatorial sums by Renzo Sprugnoli 
The concept of a Riordan array is used in a constructive way to find the generating function of many combinatorial sums. The generating function can then help us to obtain the closed form of the sum or its asymptotic value. Some examples of sums involving binomial coefficients and Stirling numbers are examined, together with an application of Riordan arrays to some walk problems. 
12.12.2019 17:00 Krzysztof Michalik 
Optymalizacja Kombinatoryczna Coloring planar graphs with 3 colors and no large monochromatic components 
I will present a proof that there exists a function f(d), such that there exists a 3coloring of any planar graph G in which each monochromatic subgraph has at most f(d) vertices, where d is the degree of the highestdegree vertex in G. 
12.12.2019 16:15 Mateusz Kaczmarek 
Optymalizacja Kombinatoryczna Hadwiger’s conjecture 
Survey of Hadwiger's Conjecture from 1943, that for all t ≥ 0, every graph is either tcolorable or has a subgraph that can be contracted to the complete t+1 vertices graph. This conjecture is the tremendous strengthening of the fourcolor problem also known as map coloring problem. 
12.12.2019 14:15 Krzysztof Pióro, Krzysztof Potępa 
Algorytmika LinearSpace Data Structures for Range Mode Query in Arrays [Chan, Durocher, Larsen, Morrison, Wilkinson] 
Modą multizbioru S nazywamy element, który występuje w S najczęściej, tzn. występuje w S co najmniej tyle razy co każdy inny element S. Mając daną nelementową tablicę A[1:n] rozważamy prosty problem: konstrukcję statycznej struktury danych pozwalającej szybko odpowiadać na zapytania o modę na przedziale A. Każde zapytanie składa się z pary (i,j), dla której odpowiedzią jest moda A[i:j]. Autorzy pracy prezentują strukturę danych z liniową pamięcią odpowiadającą na zapytania w czasie O(sqrt(n / log n)). Dodatkowo pokazują silną przesłankę, że czas zapytania zdecydowanie niższy od sqrt(n) nie może być uzyskany przy użyciu czysto kombinatorycznych technik  mnożenie macierzy logicznych rozmiaru sqrt(n) x sqrt(n) redukuje się do n zapytań o modę na przedziale w tablicy rozmiaru O(n). Autorzy prezentują też struktury danych dla ortogonalnych zapytań w wyższych wymiarach (zapytania w czasie bliskim O(n^{11/2d})) oraz zapytań o półprzestrzenie (zapytania w czasie O(n^{11/d^2})). 
11.12.2019 16:15 Adam Polak 
Informatyka Teoretyczna Monochromatic triangles, intermediate matrix products, and convolutions 
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(n^{ω}) time algorithms, for ω<2.373. On the other hand, the (min,+)product, which is at the heart of APSP, is widely conjectured to require cubic time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems, e.g. the (min,max)product, the minwitness product, APSP in directed unweighted graphs. The best runtimes for these "intermediate" problems are all O(n^{(3+ω)/2}). A similar phenomenon occurs for convolution problems.

11.12.2019 12:15 Mateusz Górski 
Podstawy Informatyki A Modal Characterization Theorem for a Probabilistic Fuzzy Description Logic by Paul Wild, Lutz Schroder, Dirk Pattinson and Barbara Konig. 
The fuzzy modality probably is interpreted over probabilistic type spaces by taking expected truth values. The arising probabilistic fuzzy description logic is invariant under probabilistic bisimilarity; more informatively, it is nonexpansive wrt. a suitable notion of behavioural distance. In the present paper, we provide a characterization of the expressive power of this logic based on this observation: We prove a probabilistic analogue of the classical van Benthem theorem, which states that modal logic is precisely the bisimulationinvariant fragment of firstorder logic. Specifically, we show that every formula in probabilistic fuzzy firstorder logic that is nonexpansive wrt. behavioural distance can be approximated by concepts of bounded rank in probabilistic fuzzy description logic. 
05.12.2019 16:15 Kornel Dulęba 
Optymalizacja Kombinatoryczna The Return of Coppersmith’s Atack: Practical Factorization of Widely Used RSA Moduli 
During the seminar I will discuss a clever attack on RSA library used in Infineon chips. Researchers discovered that the prime factors used for constructing private keys have a peculiar form. This allowed them to use a modified version of Coppersmith algorithm to recover private key basing on their public counterpart in a reasonable time for keys up to 2048 bit long. 
04.12.2019 12:15 Michał Zwonek 
Podstawy Informatyki Probably Half True: Probabilistic Satisfability over Lukasiewicz Infnitelyvalued Logic by Marcelo Finger and Sandro Preto 
We study probabilisticlogic reasoning in a context that allows for "partial truths", focusing on computational and algorithmic properties of nonclassical Lukasiewicz In nitelyvalued Probabilistic Logic. In particular, we study the satis ability of joint probabilistic assignments, which we call LIPSAT. Although the search space is initially in nite, we provide linear algebraic methods that guarantee polynomial size witnesses, placing LIPSAT complexity in the NPcomplete class. An exact satis ability decision algorithm is presented which employs, as a subroutine, the decision problem for Lukasiewicz In nitelyvalued (non probabilistic) logic, that is also an NPcomplete problem. We develop implementations of the algorithms described and discuss the empirical presence of a phase transition behavior for those implementations. 
28.11.2019 16:15 Mikołaj Twaróg 
Optymalizacja Kombinatoryczna A Short Guide to Hackenbush 
Hackenbush is a two player game played on a graph with a few marked vertices. Players alternate turns. Each turn consists of removing one edge from the graph and all vertices that lost their connection to all marked ones. Player, that can't make a move, loses. I will present three different variants of Hackenbush(RedBlue Hackenbush, Green Hackenbush and RGB Hackenbush) with methods to determine, which player has a winning strategy. Padraic Bartlett. A Short Guide to Hackenbush. VIGRE REU 2006. 
28.11.2019 14:15 Katarzyna Bułat, Dawid Tracz 
Algorytmika Parity Games: Zielonka’s Algorithm in QuasiPolynomial Time [P. Parys] 
Gry parzystości to gry pomiędzy dwoma graczami (zwyczajowo Even oraz Odd) na grafie skierowanym G = (V, E). Gracze przesuwają między wierzchołkami wirtualny token, tworząc ścieżkę. Wierzchołki grafu są etykietowane liczbami naturalnymi i każdy z nich jest przypisany do jednego gracza, który decyduje w jakim kierunku zostanie wykonany ruch z tego wierzchołka. Celem każdego z graczy jest wybranie takiej strategii, że przy nieskończonej grze (ścieżce), najwyższa nieskończenie wiele razy powtarzająca się etykieta będzie odpowiednio parzysta bądź nieparzysta. Problem gry parzystości jest deterministyczny, to znaczy dla każdego wierzchołka jeden z graczy posiada strategię wygrywającą. Rekurencyjny algorytm Zielonki rozwiązuje grę parzystości w czasie wykładniczym. Istnieje jednak algorytm działający w czasie quasiwielomianowym, czyli 2^{O((log(n))^c)} dla pewnego, ustalonego c. W trakcie prezentacji omówiony zostanie schemat nowej wersji algorytmu, przeprowadzona analiza jego złożoności oraz przedstawiony dowód poprawności zwracanego przez niego wyniku. 
27.11.2019 16:15 20.11.2019 16:15 Patryk Mikos 
Informatyka Teoretyczna Efficient enumeration of nonisomorphic interval graphs 
Recently, Yamazaki et al. provided an algorithm that enumerates all nonisomorphic interval graphs on n vertices with an O(n^{4}) time delay between the output of two consecutive graphs. We improve their algorithm and achieve O(n^{3} log n) time delay. We also extend the catalog of these graphs providing a list of all nonisomorphic interval graphs for all n up to 15 (previous best was 12). 
27.11.2019 12:15 Piotr Mikołajczyk 
Podstawy Informatyki Satisfiability in Strategy Logic can be Easier than Model Checking by Erman Acar, Massimo Benerecetti and Fabio Mogavero. 
In the design of complex systems, modelchecking and satisfiability arise as two prominent decision problems. While The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important gametheoretic properties of multiagent systems, such as existence of Nash and immune equilibria, as well as to formalize the rational synthesis problem. We show that satisfiability for such a fragment is PSPACECOMPLETE, while its modelchecking complexity is 2EXPTIMEHARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctivebinding firstorder logic, a recently discovered decidable fragment of firstorder logic. 
21.11.2019 17:00 Adrian Siwiec 
Optymalizacja Kombinatoryczna Edge Coloring Signed Graphs 
We define a method for edge coloring signed graphs and what it means for such a coloring to be proper. It then turns out that Vizing's Theorem is a special case of the more difficult theorem concerning signed graphs. 
21.11.2019 16:15 Paweł Palenica 
Optymalizacja Kombinatoryczna Guess the Larger Number 
We will discuss variations of a zero sum game where one player writes down two numbers on cards. The second player learns one of the numbers to make a guess which of the numbers is larger. We will show variations of the game where the second player has a greater chance of winning than 1/2. 
21.11.2019 14:15 Jędrzej Kula, Przemysław Simajchel 
Algorytmika Subtree Isomorphism Revisited [A. Abboud et al.] 
Problem Izomorfizmu Poddrzew zadaje pytanie, czy dane drzewo zawarte jest w innym danym drzewie. Ten problem o zasadniczym znaczeniu dla algorytmiki jest badany już od lat 60. ubiegłego wieku. Podkwadratowe algorytmy znane są dla niektórych wariantów, np. drzew uporządkowanych, ale nie w ogólnym przypadku. Poprzez redukcję z problemu Wektorów Ortogonalnych pokażemy, że prawdziwie podkwadratowy algorytm dla Izomorfizmu Poddrzew przeczy SETH. Dodatkowo pokażemy, że to samo ograniczenie dolne utrzymuje się również w przypadku ukorzenionych drzew o logarytmicznej wysokości. W opozycji do niego zaprezentujemy również podkwadratowy algorytm randomizowany dla drzew o stałym stopniu i logarytmicznej wysokości. Redukcja korzysta z nowych "gadżetów drzewowych", które prawdopodobnie przydadzą się w przyszłości w wyznaczaniu ograniczeń dolnych opartych na SETH dla problemów na drzewach. Algorytmy opierają się na znanych wynikach o złożoności randomizowanych drzew decyzyjnych. 
20.11.2019 12:15 Edyta Garbarz 
Podstawy Informatyki Unifying Logical and Statistical AI Pedro by Domingos, Daniel Lowd, Stanley Kok, Aniruddh Nath, Hoifung Poon Matthew Richardson and Parag Singla 
Intelligent agents must be able to handle the complexity and uncertainty of the real world. Logical AI has focused mainly on the former, and statistical AI on the latter. Markov logic combines the two by attaching weights to firstorder formulas and viewing them as templates for features of Markov networks. Inference algorithms for Markov logic draw on ideas from satisfiability, Markov chain Monte Carlo and knowledgebased model construction. Learning algorithms are based on the voted perceptron, pseudolikelihood and inductive logic programming. Markov logic has been successfully applied to a wide variety of problems in natural language understanding, vision, computational biology, social networks and others, and is the basis of the opensource Alchemy system. 
13.11.2019 16:15 Grzegorz Guśpiel 
Informatyka Teoretyczna Smaller Universal Targets for Homomorphisms of EdgeColored Graphs 
The density D(G) of a graph G is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D(F) is the supremum of densities of graphs in F. A kedgecolored graph is a finite, simple graph with edges labeled by numbers 1,...,k. A function from the vertex set of one kedgecolored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a kedgecolored graph H (not necessarily with the underlying graph in F) is kuniversal for F when any kedgecolored graph with the underlying graph in F admits a homomorphism to H. Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a kuniform graph for a class F is known to be Ω(k^{D(F)}) and O(k^{d}), where d is the ceiling of D(F) (result obtained in 2015 with Gutowski), and has been conjectured to be ϴ(k^{D(F)}). In this talk, I will present a construction of a kuniversal graph on O(k^{d}) vertices for any rational bound d on the density D(F). It follows that if D(F) is rational, the minimum number of vertices in a kuniversal graph for F is indeed ϴ(k^{D(F)}). 
13.11.2019 12:15 Jan Kościsz 
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 betaconversion and consider the possibility of extending Bohm's theorem to infnite RE (recursively enumerable) sets. Bohm's theorem fails in general for such sets V even if it holds for all fnite 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 with predecessor iff there is a Church delta (conditional) for V iff every Ershov morphism with domain V can be represented by a lambda term 
07.11.2019 16:15 Kamil Rajtar 
Optymalizacja Kombinatoryczna A PriceBased Iterative Double Auction for Charger Sharing Markets 
07.11.2019 14:15 Nicoll Bryła, Mateusz Pabian 
Algorytmika Faster Algorithms for All Pairs NonDecreasing Paths Problem [Duan, Jin, Wu] 
W tej pracy autorzy prezentują poprawiony algorytm dla problemu wszystkich par ścieżek niemalejących (APNP) dla grafów prostych, skierowanych i ważonych o czasie działania Õ(n^((3+ω)/2)) = Õ(n^2,686), gdzie n jest liczbą wierchołków, a ω jest wykładnikiem złożoności algorytmu szybkiego mnożenia macierzy z pracy [Williams 2012, Le Gall 2014]. To odpowiada najlepszemu, obecnemu górnemu ograniczeniu dla (max, min)iloczynu macierzy, który można zredukować do APNP. Następne usprawnienia dla APNP implikują szybszy algorytm dla (max, min)iloczynu macierzy. Poprzednie najlepsze oszacowanie górne dla ważonych, skierowanych grafów było Õ(n^(1/2(3+(3ω)/(ω+1) + ω))) = Õ(n^2,78) [Duan, Gu, Zhang 2018]. Autorzy pokazują również algorytm Õ(n^2) dla APNP w nieskierowanych, prostych grafach, który również osiąga optimum z czynnikiem logarytmicznym. 
06.11.2019 12:15 Rafał Burczyński 
Podstawy Informatyki Compaction of Church Numerals by Isamu Furuya and Takuya Kida 
In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number n, we prove that the size of the lambda term obtained by the proposed method is O((s log2n)^(log n/ (log log n))). Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when n is less than approximately 10,000 . 
30.10.2019 16:15 Bartosz Walczak 
Informatyka Teoretyczna Coloring and Maximum Weight Independent Set of rectangles 
We prove that every intersection graph of axisparallel rectangles in the plane with clique number ω has chromatic number Joint work with Parinya Chalermsook. 
30.10.2019 12:15 Jan Mełech 
Podstawy Informatyki On compressing and indexing repetitive sequences by Sebastian Kreft and Gonzalo Navarro 
We introduce LZEnd, a new member of the Lempel–Ziv family of text compressors, which achieves compression ratios close to those of LZ77 but is much faster at extracting arbitrary text substrings. We then build the first selfindex based on LZ77 (or LZEnd) compression, which in addition to text extraction offers fast indexed searches on the compressed text. This selfindex is particularly effective for representing highly repetitive sequence collections, which arise for example when storing versioned documents, software repositories, periodic publications, and biological sequence databases. 
24.10.2019 16:15 Vladyslav Rachek 
Optymalizacja Kombinatoryczna On Chromatic Number of Exact Distance Graphs 
For any graph G and positive integer p we can consider "exact distance graph" G in which vertices x and y are connected if and only if their distance in G is exactly p. We can bound chromatic number of such graphs using notion of weak coloring numbers. Proof becomes particularly valuable for odd p and planar graphs G. 
 Strona Główna
 Katedra Algorytmiki
 Katedra Podstaw Informatyki
 Wydział Matematyki i Informatyki
 Kontakt
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Galeria
 Ludzie
 Maciej Bendkowski
 Bartłomiej Bosek
 Iwona Cieślik
 Piotr Danilewski
 Jan Derbisz
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Łukasz Lachowski
 Agnieszka Łupińska
 Marcin Mazur
 Piotr Micek
 Patryk Mikos
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Maciej Ślusarek
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Byli współpracownicy