Seminaria

10.03.2021 16:15
Bartosz Walczak
Informatyka Teoretyczna
TBA - Walczak
11.03.2021 16:15
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Polynomial Treedepth Bounds in Linear Colorings

Centered graph coloring is graph coloring, such that for every connected subgraph, this subgraph contains a vertex with a unique color (we call such a vertex center). Linear coloring is coloring, such that every path has a center. We denote by cen(G) and lin(G) respectively, a minimal number of colors needed. It is obvious that lin(G) ≤ cen(G). What about the other direction? Authors of the paper show that cen f(lin), where f is a polynomial of the degree 190. Moreover, the authors conjecture that cen 2 lin for every graph. What is interesting, we don't know how to prove such abound even for trees. Luckily, for some classes of graphs, we can do better than 190-poly. During the seminar, I will present results for simple classes of graphs and I will try to sketch the general proof. In particular, I will present a cubic bound for interval graphs. The proof in the paper is incorrect, but I and dr Micek managed to fix it. Finally, I will present our new result for graphs with bounded path width.

  1. Jeremy Kun, Michael P. O’Brien, Marcin Pilipczuk, and Blair D. Sullivan. Polynomial Treedepth Bounds in Linear Colorings. Algorithmica. volume 83, pages 361–386. 2021.
  2. Jędrzej Hodor. slides. 2021.

(the seminar will only be online)

01.07.2021 16:15
Grzegorz Gutowski
Informatyka Teoretyczna
TBA - Gutowski
01.07.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 NP-complete 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.07.2021 16:15
Krzysztof Turowski
Informatyka Teoretyczna
Degree Distribution of Dynamic Graphs Generated by a Duplication-Divergence 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.
 
Joint work with Philippe Jacquet, Alan Frieze and Wojciech Szpankowski

Poprzednie referaty

25.02.2021 16:15
Kamil Kropiewnicki
Optymalizacja Kombinatoryczna
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming

We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems. This presentation might be of interest for, among the others, the participants of the Algorithmic Game Theory course as it presents the modern approach for maximizing revenue in second-price auctions.

  1. Joey Huchette, Haihao Lu, Hossein Esfandiari, Vahab Mirrokni. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. arXiv:2002.08841. 2020.
  2. Kamil Kropiewnicki. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. slides. 2021.

(the seminar will only be online)

28.01.2021 17:00
Rafał Burczyński
Optymalizacja Kombinatoryczna
Bollobás-Eldridge-Catlin Conjecture on graph packing

Let G1, G2 be n-vertex graphs. We say that they pack if they are edge-disjoint subgraphs of a complete graph on n vertices. The Bollobás-Eldridge-Catlin conjecture states that if (Δ(G1) + 1) (Δ(G2) + 1) < n + 1, then G1 and G2 pack. During the seminar, we will take a look at current results related to this problem, i.e. classes of graphs for which it has been proven as well as similar conjectures stemming from it.

  1. Rafał Burczyński. Bollobás-Eldridge-Catlin Conjecture. slides. 2021.

(the seminar will only be online)

28.01.2021 16:15
Weronika Lorenczyk
Optymalizacja Kombinatoryczna
The Cap Set Conjecture

The cap set problem asks how large can a subset of Z/3Zn be and contain no lines or, more generally, how can large a subset of Z/pZn be and contain no arithmetic progression. The problem was open until 2016 when its basic version was solved. During the lecture, we'll see the motivation for thinking about this. It appears there are some interesting applications of this result in combinatorics, geometry, and even board games.

  1. Weronika Lorenczyk. Cap Conjecture - motywacje i zastosowania. slides. 2021. (Polish)

(the seminar will only be online)

21.01.2021 17:00
Bartosz Wodziński
Optymalizacja Kombinatoryczna
Graph Removal Lemma

Let H be a graph on h vertices. The Graph Removal Lemma states that for any ε > 0, there exists a constant δ(ε, H) > 0 such that for any n-vertex graph G with fewer than δnh subgraphs isomorphic to H, it is possible to eliminate all copies of H by removing at most εn2 edges from G. It has several important consequences in number theory, discrete geometry, graph theory, and computer science.

During the seminar, I will discuss this lemma and its extensions. I will also tell about some of its applications, such as graph property testing and Szeremedi's Theorem proof.

  1. David Conlon, Jacob Fox. Graph removal lemmas. arXiv:1211.3487. 2012.
  2. Bartosz Wodziński. Graph removal lemma. slides. 2021.

(the seminar will only be online)

21.01.2021 16:15
Artur Kasymov
Optymalizacja Kombinatoryczna
Machine learning in Combinatorial Optimization

Machine learning has already leaked almost all areas. What about Combinatorial Optimization? At this seminar, I will present basic ML concepts and methods in CO: Where you can add ML black box in your algorithm? Can heuristics be compared to ML? What are the recent achievements?

  1. Artur Kasymov. Machine learning in Combinatorial Optimization. slides. 2021.

(the seminar will only be online)

20.01.2021 12:15
Weronika Loreńczyk
Podstawy Informatyki
The Fractal Dimension of SAT Formulas by Carlos Ansotegui, Maria Bonet , Jesus Giraldez-Cru and Jordi Levy
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.
14.01.2021 17:00
Bruno Pitrus
Optymalizacja Kombinatoryczna
Seven trees in one: objects of categories as complex numbers

Consider the following absurd argument concerning planar, binary, rooted, unlabelled trees. Every such tree is either the trivial tree or consists of a pair of trees joined together at the root, so the set T of trees is isomorphic to 1+T². Pretend that T is a complex number and solve the quadratic T = 1+T² to find that T is a primitive sixth root of unity and so T⁶ = 1. Deduce that T⁶ is a one-element set; realize immediately that this is wrong. Notice that T⁷ = T is, however, not obviously wrong, and conclude that it is therefore right. In other words, conclude that there is a bijection T⁷ ≅ T built up out of copies of the original bijection T ≅ 1+T²: a tree is the same as seven trees.

  1. Andreas Blass. Seven Trees in One. arXiv:math/9405205. 1994.
  2. Marcelo Fiore, Tom Leinster. Objects of Categories as Complex Numbers. arXiv:math/0212377. 2002.
  3. Bruno Pitrus. Seven trees in one: objects of categories as complex numbers. slides. 2021.

(the seminar will only be online)

14.01.2021 16:15
Krzysztof Pióro
Optymalizacja Kombinatoryczna
Gallai’s conjecture

A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most ⌈n/2⌉. Gallai’s Conjecture has been verified for many classes of graphs. In this seminar, we will cover some of these graph classes.

  1. Krzysztof Pióro. Hipoteza Gallai. slides. 2020.

(the seminar will only be online)

13.01.2021 12:14
Maciej Nemś
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.
07.01.2021 16:15
Szymon Żak
Optymalizacja Kombinatoryczna
Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes

In this seminar, I will cover general ideas that stand behind Aleph protocol. Aleph is a leaderless, fully asynchronous, Byzantine fault tolerant consensus protocol for ordering messages exchanged among processes. It is based on a distributed construction of a partially ordered set and the algorithm for reaching a consensus on its extension to a total order.

  1. Adam Gągol, Michał Świetek. Aleph: A Leaderless, Asynchronous, Byzantine Fault Tolerant Consensus Protocol. arXiv:1810.05256. 2018.
  2. Adam Gągol, Damian Leśniak, Damian Straszak, Michał Świetek. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. arXiv:1908.05156. 2019.
  3. Adam Gągol, Damian Straszak. Blockchain Fundamentals. 2020.
  4. Szymon Żak. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. slides. 2021.

(the seminar will only be online)

17.12.2020 17:00
Jan Mełech
Optymalizacja Kombinatoryczna
Hamiltonian paths/cycles in vertex-transitive/symmetric graphs

Graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on the vertices and edges surrounding it. In 1969, Lovasz conjectured that every finite connected vertex-transitive graph has Hamiltonian path. Moreover, up to now there are currently only five known connected vertex-transitive graphs not containing Hamiltonian cycle. In this seminar we will focus also on some other weaker variants of Lovasz conjecture related to other interesting class of graphs that encode the abstract structures of a groups - Cayley graphs.

  1. Jan Mełech. Hamiltonian paths/cycles in vertex-transitive/symmetric graphs. slides. 2020.

(the seminar will only be online)

17.12.2020 16:15
Mateusz Kaczmarek
Optymalizacja Kombinatoryczna
From linear lambda terms to rooted trivalent maps

Recent work on the combinatorics of the linear lambda term shows that it has various connections to the theory of graph surfaces (maps). Based on paper [1] I will present a bijection between linear lambda terms (presented as diagrams) and rooted trivalent maps. Also, I will cover the recent conjecture proposed in 2019 that a special class of planar lambda terms can be counted the same way that rooted bicubic maps.

  1. Noam Zeilberger. Linear lambda terms as invariants of rooted trivalent maps. arXiv:1512.06751. 2015.
  2. Mateusz Kaczmarek. From linear lambda terms to rooted trivalent maps. slides. 2020.

(the seminar will only be online)

16.12.2020 12:15
Weronika Loreńczyk - canceled
Podstawy Informatyki
The Fractal Dimension of SAT Formulas by Carlos Ansotegui, Maria Bonet , Jesus Giraldez-Cru and Jordi Levy
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.
10.12.2020 17:00
Wojciech Buczek
Optymalizacja Kombinatoryczna
Inscribed square problem

Let C be a Jordan curve. We say that polygon P is inscribed in C if all vertices of P belong to C. In the inscribed square problem we ask if every Jordan curve admits an inscribed square. It's also known as "Toeplitz’s conjecture" or the "Square peg problem". In this seminar, we will show some equivalent problems to this conjecture and focus on special cases of the Jordan curves.

  1. Wojciech Buczek. Inscribed square problem. slides. 2020.

(the seminar will only be online)

10.12.2020 16:15
Bartłomiej Jachowicz
Optymalizacja Kombinatoryczna
Parameterized by treewidth algorithms for Hamiltonian Cycle

The Hamiltonian Cycle problem is one of the oldest and most common NP-complete problems. It consists of checking whether in a given graph there is a cycle visiting each vertex exactly once. I will present a parameterized algorithm based on graph tree decomposition. Assuming that a nice tree decomposition of the width k is known at the input Hamiltonian cycle problem can be solved in a time 2(O(k))n(O(1)).

  1. Bartłomiej Jachowicz. Parameterized by treewidth algorithms for Hamiltonian Cycle. slides. 2020.

(the seminar will only be online)

10.12.2020 14:15
Jacek Salata, Krzysztof Ziobro
Algorytmika
A New Upper Bound for Separating Words
09.12.2020 12:14
Katarzyna Król
Podstawy Informatyki
A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods by Mirai Ikebuchi
It is well-known that some equational theories such as groups or boolean algebras can be defined by fewer equational axioms than the original axioms. However, it is not easy to determine if a given set of axioms is the smallest or not. Malbos and Mimram investigated a general method to find a lower bound of the cardinality of the set of equational axioms (or rewrite rules) that is equivalent to a given equational theory (or term rewriting systems), using homological algebra. Their method is an analog of Squier’s homology theory on string rewriting systems. In this paper, we develop the homology theory for term rewriting systems more and provide a better lower bound under a stronger notion of equivalence than their equivalence. The author also implemented a program to compute the lower bounds.
03.12.2020 17:00
Michał Zwonek
Optymalizacja Kombinatoryczna
Approximate Distance Oracles

Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v∈V, returns an approximation to the actual distance between u and v which is within some bounded stretch factor of the true distance. The first work in this area was done by Mikkel Thorup and Uri Zwick, they devised an oracle with construction time being O(kmn(1/k)) and with the space complexity of O(kn(1+1/k)). The achieved stretch, that is the measure of how accurate the answer by the approximate oracle will be, is bounded by (2k-1). The query time is O(k), this has been subsequently improved to O(log n) by Wulff-Nilsen and to O(1) by Shiri Chechik.

  1. Michał Zwonek. Approximate Distance Oracles. slides. 2020.

(the seminar will only be online)

03.12.2020 16:15
Wojciech Grabis
Optymalizacja Kombinatoryczna
Double-critical graph conjecture

A connected graph G is called double-critical if the chromatic number of G decreases by two if any two adjacent vertices of G are removed. In 1966, Erdős and Lovász conjectured that the only double-critical n-chromatic graph is the complete graph on n vertices. During the seminar, I will present what has been verified about the conjecture.

  1. Wojciech Grabis. Double-critical graph conjecture. slides. 2020.

(the seminar will only be online)

03.12.2020 14:15
Rafał Kilar, Szymon Salabura
Algorytmika
Tetris is NP-hard even with O(1) rows or columns
02.12.2020 12:14
Wojciech Węgrzynek
Podstawy Informatyki
The repetition threshold for binary rich words by James Currie, Lucas Mol and Narad Rampersad
A word of length n is rich if it contains n nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent  $2 + \Sqrt{2}/2$ ( = 2.707) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is $2 + \Sqrt{2}/2$ ). In this article, we give a structure theorem for infinite binary rich words that avoid 14/5-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is $2 + \Sqrt{2}/2$  , as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets.

 

26.11.2020 17:00
Krzysztof Potępa
Optymalizacja Kombinatoryczna
Erdős–Hajnal conjecture

A well-known theorem of Erdős states that there exists a graph on n vertices, with no clique or independent set of a size larger than O(log n). The Erdős–Hajnal conjecture says it is very different if we consider families of graphs defined by forbidden induced subgraphs. Specifically, it is conjectured that for every graph H, there exists a constant δ(H) such that every H-free graph G has either a clique or independent set of size |V(G)|δ(H). We will discuss some classes of graphs for which the conjecture has been proven, as well as weaker theorems that hold for all graphs.

  1. Krzystzof Potępa. The Erdős–Hajnal conjecture. slides. 2020.

(the seminar will only be online)

26.11.2020 16:15
Marcin Serwin
Optymalizacja Kombinatoryczna
(m,n)-cycle cover conjectures

An (m,n)-cycle cover is a covering of a graph consisting of m cycles such that every edge is covered exactly n times. For positive integers m, n it is natural to ask what family of graphs have (m,n)-cycle covers. The answers are known for some values, but for many others, they are conjectured or totally open.

  1. Marcin Serwin. (m,n)-cycle cover conjectures. slides. 2020.

(the seminar will only be online)

26.11.2020 14:15
Jan Mełech, Michał Zwonek
Algorytmika
On the Fine-Grained Complexity of Parity Problems
25.11.2020 12:14
Wojtek Grabis
Podstawy Informatyki
(Optimal) Duplication is not Elementary Recursive by Andrea Asperti, Paolo Coppola and Simone Martini
In 1998 Asperti and Mairson proved that the cost of reducing a lambda-term using an optimal lambda-reducer (a la L´evy) cannot be bound by any elementary function in the number of shared-beta steps. We prove in this paper that an analogous result holds for Lamping’s abstract algorithm. That is, there is no elementary function in the number of shared beta steps bounding the number of duplication steps of the optimal reducer. This theorem vindicates the oracle of Lamping’s algorithm as the culprit for the negative result of Asperti and Mairson. The result is obtained using as a technical tool Elementary Affine Logic.
19.11.2020 14:15
Łukasz Selwa, Juliusz Wajgelt
Algorytmika
Compact Distributed Certification of Planar Graphs
18.11.2020 12:14
Michał Zwonek
Podstawy Informatyki
A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy by JAKOB GRUE SIMONSEN
A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.
12.11.2020 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Harmonious Coloring of Hypergraphs

A harmonious coloring of a k-uniform hypergraph H is a vertex coloring such that no two vertices in the same edge share the same color, and each k-element subset of colors appears on at most one edge. The harmonious number h(H) is the least number of colors needed for such a coloring. We prove that k-uniform hypergraphs of bounded maximum degree Δ satisfy h(H) = O(k√k!m), where m is the number of edges in H which is best possible up to a multiplicative constant. Moreover, for every fixed Δ, this constant tends to 1 with k → ∞. We use a novel method, called entropy compression, that emerged from the algorithmic version of the Lovász Local Lemma due to Moser and Tardos. This is joint work with Sebastian Czerwinski, Jarosław Grytczuk, and Paweł Rzazewski.

  1. Bartłomiej Bosek, Jarosław Grytczuk, Paweł Rzążewski, Sebastian Czerwiński. Harmonious coloring of uniform hypergraphs. Applicable Analysis and Discrete Mathematics, 10(1), 73-87, 2016.

(the seminar will only be online)

12.11.2020 14:15
Dzianis Pivavarau, Dominik Wielgórski
Algorytmika
Explicit two-deletion codes with redundancy matching the existential bound
05.11.2020 16:15
Piotr Mikołajczyk
Optymalizacja Kombinatoryczna
Polynomial algorithms for CFGs via semiring embeddings

A few years ago M. Might et al. published somehow unusual approach to parsing context-free grammars by using derivative operator. Later it was proven, that its worst case complexity is polynomial, putting it on a par with other classical approaches. We introduce an elegant generalization to this method by a generic algorithm parametrized with a semiring. Depending on the chosen algebra we can obtain polynomial algorithms for problems like parsing, recognizing or counting parse trees for CFGs.

  1. Piotr Mikołajczyk. Polynomial algorithms for CFGs via semiring embedding. slides. 2020.

(the seminar will only be online)

05.11.2020 14:15
Bartłomiej Jachowicz, Mateusz Kaczmarek
Algorytmika
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
04.11.2020 12:14
Przemysław Simajchel
Podstawy Informatyki
COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PAK
The paper gives a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.
29.10.2020 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Majority choosability of digraphs

One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24(3), Paper 3.57, 2017.
  6. António Girao, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Samal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15–20, 2019.

(the seminar will only be online)

29.10.2020 14:15
Lech Duraj
Algorytmika
Range queries and triangles
28.10.2020 12:14
CANCELED
Podstawy Informatyki
COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PAK
The paper gives a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.
22.10.2020 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Conjecture 1/3 - 2/3

A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field.

(the seminar will only be online)

22.10.2020 14:15
Marcin Serwin, Wojciech Buczek
Algorytmika
A Double-Exponential Lower Bound for the Distinct Vectors Problem
21.10.2020 12:15
Piotr Mikołajczak
Podstawy Informatyki
Asymptotic Approximation by Regular Languages by Ryoma Sin’ya
This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language L is REG-measurable if there exists an infinite sequence of regular languages that “converges” to L. A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. We show that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain  simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense.
15.10.2020 16:15
Vladyslav Rachek
Optymalizacja Kombinatoryczna
Small weak epsilon-nets

Let P be a set of n points in R2, ε > 0. A set of points Q is called a weak ε-net for P with respect to a family S of objects (e.g. axis-parallel rectangles or convex sets) if every set from S containing more than εn points of P contains a point from Q. Let R be the family of all axis-parallel rectangles in R2 and εRk be the smallest real number such that for any P there exists a weak εRk-net of size k. The work by Aronov et al. suggests that the inequality εRk ≤ 2/(k+3) may hold. In this talk we present the complete proofs of this inequality for k=1,...,5 and prove that this bound is tight for k=1,2,3. Besides, it is not clear how to construct optimal nets. Langerman conjectured that k-point 2/(k+3)-nets can be chosen from some speciffc set of points which are the intersections of grid lines, where the grid is of size k×k. We give counterexamples to this conjecture for nets of size 3 through 6.

  1. Vladyslav Rachek. Small weak epsilon-nets in families of rectangles. Bachelor's Thesis. Jagiellonian University. 2020.
  2. B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, C.Seara, and S. Smorodinsky. Small weak epsilon-nets. Computational Geometry: Theory and applications. 42(5), 2009. pp. 455-462.
  3. Vladyslav Rachek. On small weak epsilon-nets for axis-parallel rectangles. slides. 2020.

(the seminar will only be online)

15.10.2020 14:15
Krzysztof Pióro, Krzysztof Potępa
Algorytmika
Modular Subset Sum
W problemie Modular Subset Sum dane są liczba naturalna m, n-elementowy multizbiór S liczb całkowitych z zakresu od 0 do m-1 oraz liczba t, dla której chcemy rozstrzygnąć, czy istnieje podzbiór S, który się do niej sumuje modulo m.
 
Przedstawimy własne algorytmy rozwiązujące powyższy problem. Wszystkie z nich będą sprowadzały problem Modular Subset Sum do problemu tekstowego. Na początku przedstawimy prosty algorytm działający w czasie O(n + m*log2(m)) wykorzystujący haszowanie i drzewa przedziałowe. Następnie pokażemy jak poprawić jego złożoność do O(n + m*log(m)). Na końcu zaprezentujemy w pełni deterministyczny wariant algorytmu działający w czasie O(n + m*log(m)*α(m)).
14.10.2020 12:15
Jędrzej Hodor
Podstawy Informatyki
Bijective link between Chapoton’s new intervals and bipartite planar maps by Wenjie Fang
In 2006, Chapoton defined a class of Tamari intervals called “new intervals” in his enumeration of Tamari intervals, and he found that these new intervals are equienumerated with bipartite planar maps. We present here a direct bijection between these two classes of objects using a new object called “degree tree”. Our bijection also gives an intuitive proof of an unpublished equi-distribution result of some statistics on new intervals given by Chapoton and Fusy.
08.10.2020 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
From the 1-2-3 Conjecture to the Riemann Hypothesis

A series of open (and solved) problems will be presented at the seminar, starting with the 1-2-3 Conjecture and ending with the Riemann Hypothesis.

  1. Jarosław Grytczuk. From the 1-2-3 conjecture to the Riemann hypothesis. European Journal of Combinatorics, 91, 2021, 103213.

(the seminar will only be online)

08.10.2020 12:00
Patryk Mikos
Informatyka Teoretyczna
Geometric and weight constraints in Online Interval Coloring
PhD defense - room 0004
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 NP-complete problems, there is a huge gap between best-known 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 so-called Unique Games Conjecture was formulated by Khot. It states that having a (1-𝜀)-satisfiable instance of Unique Label Cover problem, it is NP-hard 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 Goemans-Williamson Algorithm for Max-Cut 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.

  1. Subhash Khot. On the Unique Games Conjecture (Invited Survey). 2010 IEEE 25th Annual Conference on Computational Complexity, Cambridge, MA, 2010, pp. 99-121.
  2. Bartosz Wodziński. Unique Games Conjecture. slides. 2020.

(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.

  1. Gabriela Czarska. Lonely runner conjecture. slides. 2020.

(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 |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 genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter 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 genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter 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 genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter 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 genus-based hierarchies of regular languages and in particular, we
show a new family of regular languages on a two-letter 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 zero-divisor 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 zero-divisors 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.

  1. D. Bennis, J. Mikram, and F. Taraz. On the extended zero divisor graph of commutative rings. Turkish Journal of Mathematics. 40, 376-388, 2016.
  2. P. Dankelmann, J. D. Key, and B. G. Rodrigues. Codes from incidence matrices of graphs. Des. Codes Cryptogr. 68, 373-393, 2013.
  3. D. F. Anderson, P. S. Livingston. The Zero-Divisor Graph of a Commutative Ring. Journal of Algebra. 217(2), 434-447 , 1999.
  4. Raja L'hamri.Codes from zero-divisor graphs. slides. 2020.

(the seminar will only be online)

03.06.2020 12:15
Ruslan Yevdokymov
Podstawy Informatyki
Learnability can be undecidable by Shai Ben-David, 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 1-2-3 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 1-2-3 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.

  1. Michał Stobierski. The 1-2-3 Conjecture. slides. 2020.

(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 G2 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+ 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 8-colorable. He conjectured that his bound can be improved - the chromatic number of G2 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 χ(G2) ≤ 9D-19, for planar graphs with D ≥ 5. Agnarsson and Halldorson showed that for every planar graph G with maximum degree D ≥ 749, χ(G2) ≤ [9D / 5] + 2. Van den Heuvel and McGuinness (2003) showed that χ(G2) ≤ 2D + 25, Bordin (2002) proved that χ(G2) ≤ [9D / 5] + 1, if D ≥ 47, and Molloy and Salavatipour (2005) proved χ(G2) ≤ [5D / 3] + 78, moreover, χ(G2) ≤ [5D / 3] + 25 if D ≥ 241. Moreover, conjecture is confirmed in the case of outerplanar graphs and graphs without K4 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.

  1. Rafał Byczek. Wegner’s conjecture Colouring the square of a planar graph. slides. 2020.

(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 prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known 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 length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free 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 prefix-free 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 prefix-free 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.

  1. Andrzej Kaczmarczyk, Piotr Faliszewski. Algorithms for Destructive Shift Bribery. arXiv:1810.01763. 2018.
  2. Wojtek Grabis. Conflict-free Replicated Data Types. slides. 2020.

(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 call-by-value and call-by-name 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 well-known bounds in a simpler way or new improved bounds in some special cases, including regular graphs.

  1. Sharareh Alipour, Amir Jafari. Upper Bounds for the Domination Numbers of Graphs Using Turán’s Theorem and Lovász Local Lemma. Graphs and Combinatorics35, 2019, 1153-1160.
  2. Jan Mełech. Upper bounds for domination number. slides. 2020.

(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
3-flow conjecture

3-flow-conjecture
“Every 4-edge-connected graph has a nowhere-zero 3-flow.”

Grötzsch proved that every triangle free (and loopless) planar graph is 3-colorable. By flow/coloring duality, this is equivalent to the statement that every 4-edge-connected planar graph has a nowhere-zero 3-flow. The 3-flow conjecture asserts that this is still true without the assumption of planarity.

Jaeger proved that 4-edge-connected graphs have nowhere-zero 4-flows. The following weak version of the 3-flow conjecture used to remain open until 2010, but the original 3-flow conjecture remains wide open.

C̶o̶n̶j̶e̶c̶t̶u̶r̶e̶ (The weak 3-flow conjecture (Jaeger))
“There exists a fixed integer k so that every k-edge-connected graph has a nowhere-zero 3-flow.” 

These problems and the surrounding results will be presented during the seminar.

  1. Carsten Thomassen. The weak 3-flow conjecture and the weak circular flow conjecture. Journal of Combinatorial Theory, Series B102(2), 2012, 521-529.
  2. Fuyuan Chen, Bo Ning. A note on nowhere-zero 3-flow and Z_3-connectivity. arXiv:1406.1554. 2014.
  3. Michał Zwonek. Nowhere Zero Flow and related open problems, slides. 2020.

(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ás-Sumner conjecture or χ-boundedness connection to Erdős-Hajnal conjecture.

  1. Alex Scott, Paul Seymour. A survey of χ-boundedness. arXiv:1812.07500. 2018.
  2. Mateusz Kaczmarek. χ-boundedness, slides. 2020.

(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.

  1. John Voight. On the nonexistence of odd perfect numbers. MASS selecta, 293–300, Amer. Math. Soc., Providence, RI, 2003.
  2. Kornel Dulęba. Perfect Numbers. slides. 2020.

(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.

  1. Clayton Barnes II. The Lonely Runner Conjecture. arXiv:1211.2482. 2012.
  2. Thomas W. Cusick, Jorg M. Wills. Lonely runner conjecture. Open Problem Garden. 2007.
  3. Bartłomiej Jachowicz. Lonely Runner Conjecture. slides. 2020.

(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.

  1. William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey. arXiv:1308.3385. 2013.
  2. Filip Bartodziej. Meyniel’s conjecture. slides. 2020.

(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 n-state 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.

  1. Mikhail V. Volkov. Synchronizing Automata and the Černý Conjecture. LATA 2008. 11-27.
  2. Mateusz Pabian. Synchronizing Automata and the Černý Conjecture. slides. 2020.

(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 well-studied online problems such as ski rental, online bidding, bin packing, and list update.

  1. Spyros Angelopoulos, Christoph Durr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. arXiv:1905.05655. 2019.
  2. Adrian Siwiec. Online Computation with Untrusted Advice. slides. 2020.

(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 finite-rank 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 friends-of-friends as friends. We will say about Chen-Shen-Yuster 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.

  1. Salman Ghazal. Seymour's second neighborhood conjecture for tournaments missing a generalized star. arXiv:1106.0085, 2011.
  2. Tyler Seacrest. Seymour's Second Neighborhood Conjecture for Subsets of Vertices. arXiv:1106.0085, 2018.
  3. Wojciech Buczek. Seymour’s Second Neighbourhood Conjecture. slides. 2020.

(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.

  1. Mikołaj Twaróg. Collatz conjecture. slides. 2020.

(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 well-known 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 pre-processed to clause normal form. Sequent calculus, on the other hand, is a modular formalism that is useful for analysing meta-properties of various logics and is, therefore, popular among proof theorists. The input problem does not need to be pre-processed, 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.

  1. Aviezri S. Fraenkel, Edward R. Scheinerman, Daniel Ullman. Undirected Edge Geography. Theoretical Computer Science112(2), 1993, 371-381.
  2. Adam Pardyl. Undirected edge geography. slides. 2020.

(the seminar will only be online)