Seminaria

07.12.2022 12:14
Katarzyna Król
Podstawy Informatyki
Universal Skolem Sets by Florian Luca, Joel Ouaknine, and James Worrell
It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences, namely whether a given such sequence has a zero term. In this paper we introduce the notion of a Universal Skolem Set: an infinite subset S of the positive integers such that there is an effective procedure that inputs a linear recurrence sequence u = (u(n))n0 and decides whether u(n) = 0 for some n S . The main technical contribution of the paper is to exhibit such a set
07.12.2022 16:15
László Végh
London School of Economics
Informatyka Teoretyczna
Interior point methods are not (much) worse than Simplex

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2n n1.5 log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

The number of iterations of our algorithm is at most O(n1.5 log n) times the number of segments of any piecewise linear curve in the wide neighbourhood of the central path. In particular, it matches the number of iterations of any path-following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths.

This is joint work with Xavier Allamigeon (INRIA/Ecole Polytechnique), Daniel Dadush (CWI Amsterdam), Georg Loho (U Twente), and Bento Natura (LSE/Georgia Tech).

08.12.2022 16:00
Rafał Kilar
Optymalizacja Kombinatoryczna
Minimal Non-Two-Colorable Hypergraphs and Minimal Unsatisfiable Formulas
  1. Ron Aharoni, Nathan Linial. Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. Journal of Combinatorial Theory, Series A. 4(2), 196-204. (1986).
  2. Rafał Kilar. slides. (2022).
08.12.2022 16:45
Grzegorz Gawryał
Optymalizacja Kombinatoryczna
On topological aspects of orientations
  1. H. de Fraysseix, P. Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics. 229(1-3), 57-72. (2001).
  2. Grzegorz Gawryał. slides. (2022).
14.12.2022 12:14
Filip Jasiński
Podstawy Informatyki
A Universal Skolem Set of Positive Lower by Density Florian Luca, Joël Ouaknine and James Worrell
The Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set – a set of positive integers relative to which the Skolem Problem is decidable. More precisely, S is a Skolem set for a class L of integer LRS if there is an effective procedure that, given an LRS in L, decides whether the sequence has a zero in S. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present work we construct a Skolem set of positive lower density for the class of simple LRS.
14.12.2022 16:15
Boris Bukh
Carnegie Mellon
Informatyka Teoretyczna
Extremal graphs without exponentially-small bicliques

In 1954 Kővári, Sós, and Turán showed that every n-vertex graph not containing Ks,t has at most O(n2−1/s) edges. We construct graphs matching this bound with t≈9s, improving on factorial-type bounds. In this talk, I will explain probabilistic and geometric ideas behind the construction.

15.12.2022 16:00
Tomasz Mazur
Optymalizacja Kombinatoryczna
Improved lower bound for the list chromatic number of graphs with no Kt minor
  1. Raphael Steiner. Improved lower bound for the list chromatic number of graphs with no Kt minor. arXiv:2110.09403. (2021).
  2. Tomasz Mazur. slides. (2022).
15.12.2022 16:45
Hubert Zięba
Optymalizacja Kombinatoryczna
The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture
  1. Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang. The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B. 121, 308-325. (2016).
  2. Hubert Zięba. slides. (2022).
21.12.2022 12:14
Łukasz Grobelczyk
Podstawy Informatyki
Bijections between planar maps and planar linear normal \lambda-terms with connectivity condition by Wenjie Fang
The enumeration of linear λ-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal λ-terms and planar maps, which, when restricted to 2-connected λ-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal λ-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal λ-terms and planar maps, whose restriction to 2-connected λ-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.
21.12.2022 16:15
Ross Kang
University of Amsterdam
Informatyka Teoretyczna
TBA - Ross Kang
04.01.2023 12:14
Sebastain Spyrzewski
Podstawy Informatyki
A characterization of lambda-terms transforming numerals by PAWEŁ PARYS
It is well known that simply typed λ-terms can be used to represent numbers, as well as some other data types. We show that λ-terms of each fixed (but possibly very complicated) type can be described by a finite piece of information (a set of appropriately defined intersection types) and by a vector of natural numbers. On the one hand, the description is compositional:
having only the finite piece of information for two closed λ-terms M and N, we can determine its counterpart for M N, and a linear transformation that applied to the vectors of numbers for M and N gives us the vector for M N. On the other hand, when a λ-term represents a natural number, then this number is approximated by a number in the vector corresponding to this λ-term. As a consequence, we prove that in a λ-term of a fixed type, we can store only a fixed number of natural numbers, in such a way that they can be extracted using λ-terms. More precisely, while representing k numbers in a closed λ-term of some type, we
only require that there are k closed λ-terms M1, . . . , M k such that M i takes as argument the λ-term representing the k-tuple, and returns the i-th number in the tuple (we do not require that, using λ-calculus, one can construct the representation of the k-tuple out of the k numbers in the tuple). Moreover, the same result holds when we allow that the numbers can be extracted approximately, up to some error (even when we only want to know whether a set is bounded or not). All the results remain true when we allow the Y combinator (recursion) in our λ-terms, as well as uninterpreted constants.
04.01.2023 16:15
Michał Pilipczuk
University of Warsaw
Informatyka Teoretyczna
TBA - Michał Pilipczuk
05.01.2023 16:00
Aleksander Katan
Optymalizacja Kombinatoryczna
A generalization of Konig's theorem
  1. L. Lovász. A generalization of Kónig's theorem. Acta Mathematica Academiae Scientiarum Hungaricae. 21, 443-446. (1970).
  2. Aleksander Katan. slides. (2022).
05.01.2023 16:45
Jakub Siuta
Optymalizacja Kombinatoryczna
On Induced Subgraphs with All Degrees Odd
  1. A.D. Scott. On Induced Subgraphs with All Degrees Odd. Graphs and Combinatorics. 17, 539-553. (2001).
  2. Jakub Siuta. slides. (2022).
11.01.2023 12:14
Rafał Loska
Podstawy Informatyki
Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study by Olivier Bodini, Antoine Genitrini, Cécile Mailler and Mehdi Naima
In this paper we study two models of labelled random trees that generalise the original unlabelled Schroder tree. Our new models can be seen as models for phylogenetic trees in which nodes represent species and labels encode the order of appearance of these species, and thus the chronology of evolution. One important feature of our trees is that they can be generated
efficiently thanks to a dynamical, recursive construction. Our first model is an increasing tree in the classical sense (labels increase along each branch of the tree and each label appears only once). To better model phylogenetic trees, we relax the rules of labelling by allowing repetitions in the second model. For each of the two models, we provide asymptotic theorems for different characteristics of the tree (e.g. degree of the root, degree distribution, height, etc), thus giving extensive information about the typical shapes of these trees. We also provide efficient algorithms to generate large trees efficiently in the two models. The proofs are based on a combination of analytic combinatorics, probabilistic methods, and bijective methods (we exhibit bijections between our models and well-known models of the literature such as permutations and Stirling numbers of both kinds). It turns out that even though our models are labelled, they can be specified simply in the world of ordinary generating functions. However, the resulting generating functions will be formal. Then, by applying Borel transforms the models will be amenable to techniques of analytic combinatorics.
11.01.2023 16:15
Jonathan Narboni
Jagiellonian
Informatyka Teoretyczna
TBA - Jonathan Narboni
12.01.2023 16:00
Katzper Michno
Optymalizacja Kombinatoryczna
On the discrepancy of circular sequences of reals
  1. Fan Chung, Ron Graham. On the discrepancy of circular sequences of reals. Journal of Number Theory. 164, 52-65. (2016).
  2. Katzper Michno. slides. (2022).
12.01.2023 16:45
Julia Biały
Optymalizacja Kombinatoryczna
Can a party represent its constituency?
  1. Amoz Kats. Can a party represent its constituency? Public Choice. 44, 453-456. (1984).
  2. Julia Biały. slides. (2022).
18.01.2023 12:14
Roman Madej
Podstawy Informatyki
Modular Construction of Fixed Point Combinators and Clocked Bohm Trees by Jorg Endrullis, Dimitri Hendriks and Jan Willem Klop

Fixed point combinators (and their generalization: looping combinators) are classic notions belonging to the heart of λ-calculus and logic. We start with an exploration of the structure of fixed point combinators (fpc’s), vastly generalizing the well-known fact that if Y is an fpc, Y (SI) is again an fpc, generating the B ̈ohm sequence of fpc’s. Using the infinitary λ-calculus we devise infinitely many other generation schemes for fpc’s. In this way we find schemes and building blocks to construct new fpc’s in a modular way. Having created a plethora of new fixed point combinators, the task is to prove that they are indeed new. That is, we have to prove their β-inconvertibility. Known techniques via B ̈ohm Trees do not apply, because all fpc’s have the same Bohm Tree (BT). Therefore, we employ ‘clocked BT’s’, with annotations that convey information of the tempo in which the data in the BT are produced. BT’s are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for λ-terms. The corresponding equality is strictly intermediate between =β and =BT, the equality in the classical models of λ-calculus. An analogous approach pertains to L ́evy–Longo and Berarducci trees. Finally, we increase the discrimination power by a precision of the clock notion that we call ‘atomic clock’.


The theory of sage birds (technically called fixed point combinators) is a fascinating and basic part of combinatory logic; we have only scratched the surface.

18.01.2023 16:15

Informatyka Teoretyczna
TBA - 18.01
19.01.2023 16:00
Jakub Dziarkowski
Optymalizacja Kombinatoryczna
Note on Perfect Forests
  1. Gregory Gutin. Note on Perfect Forests. arXiv:1501.01079. (2015).
  2. Jakub Dziarkowski. slides. (2022).
25.01.2023 12:14
Krzysztof Barański
Podstawy Informatyki
A verified framework for higher-order uncurrying optimizations by Zaynah Dargaye and Xavier Leroy
Function uncurrying is an important optimization for the efficient execution of functional programming languages. This optimization replaces curried functions by uncurried, multiple-argument functions, while preserving the ability to evaluate partial applications. First-order uncurrying (where curried functions are optimized only in the static scopes of their definitions) is well understood and implemented by many compilers, but its extension to higher-order functions (where uncurrying can also be performed on parameters and results of higher-order functions) is challenging. This article develops a generic framework that expresses higher-order uncurrying optimizations as type-directed insertion of coercions, and prove its correctness. The proof uses step-indexed logical relations and was entirely mechanized using the Coq proof assistant.
25.01.2023 16:15
Andrzej Grzesik
Jagiellonian
Informatyka Teoretyczna
TBA - Andrzej Grzesik
02.03.2023 16:15

Informatyka Teoretyczna
TBA - 03.02

Poprzednie referaty

01.12.2022 16:45
Szymon Salabura
Optymalizacja Kombinatoryczna
Farey sequence and Graham’s conjectures
  1. Liuquan Wang. Farey sequence and Graham's conjectures. arXiv:2005.04429. (2020).
  2. Szymon Salabura. slides. (2022).
01.12.2022 16:00
Katarzyna Kępińska
Optymalizacja Kombinatoryczna
Color-Critical Graphs on a Fixed Surface
  1. Carsten Thomassen. Color-Critical Graphs on a Fixed Surface. Journal of Combinatorial Theory, Series B. 70(1), 67-100. (1997).
  2. Katarzyna Kępińska. slides. (2022).
01.12.2022 14:15
Tomasz Mazur, Katzper Michno
Algorytmika
Constrained Backward Time Travel Planning is in P
Tematem rozważań będą sieci transportowe modelowane przez dynamiczne grafy, w których wierzchołkach dopuszczalne jest cofanie się w czasie, przy czym nie można cofnąć się o więcej niż pewną liczbę jednostek oraz jest ono obarczone kosztem wyrażonym pewną funkcją kosztu. Skupiamy się na dynamicznych grafach będącymi podgrafami ścieżki. W szczególności podajemy algorytmy wielomianowe dla różnych wariantów szukania trasy z jednego wierzchołka do drugiego minimalizującej w pierwszej kolejności opóźnienie (różnicę między  czasem dotarcia a wyruszenia), a drugiej sumaryczny koszt cofania się w czasie. Warianty różnią się ograniczeniami na to, jak możemy cofać się w czasie. 
Badamy wpływ wyboru funkcji kosztu cofania na problem obliczania optymalnej trasy oraz podajemy warunki konieczne dla funkcji kosztu, aby optymalna trasa istniała. Na koniec podajemy optymalny algorytm on-line na szukanie optymalnej trasy dla funkcji kosztu będącej identycznością, w przypadku, gdy możemy cofać się dowolnie daleko w czasie.
30.11.2022 16:15
Małgorzata Sulkowska
Wrocław University of Technology
Informatyka Teoretyczna
Modularity of minor-free graphs
Modularity is a well-established parameter measuring the presence of community structure in the graph. It was introduced by Newman and Girvan in 2004. Nowadays it is widely used as a quality function for community detection algorithms. The popular heuristic clustering algorithms (e.g., Louvain algorithm or Leiden algorithm) find a partition using modularity-based approach. We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, for every ε>0, the modularity of any graph in the class with sufficiently many edges is at least 1−ε. This completes the classification of maximally modular classes among all commonly considered subclasses of nowhere dense graphs with maximum degree sublinear in the number of edges.
 
Joint work with Michał Lasoń
30.11.2022 12:14
Tomasz Buczyński
Podstawy Informatyki
The Variable Containment Problem by Stefan Kahrs

The essentially free variables of a term t in some lambda calculus $FV(t)$ form the set $\{x : \forall t =_{beta} u \rightarrow x\in FV(u) \}. This set is signicant once we consider equivalence classes of \lambda terms rather than \lambda terms themselves as for instance in higher order rewriting. An important problem for (generalised) higher order rewrite systems is the variable containment problem. This property is important when we want to consider $t \rightarrow u$ as a rewrite rule and keep n-step rewriting decidable. Variable containment is in general not implied by $FV(t) \supseteq FV(u)$. We give a decision procedure for the variable containment problem of the second order fragment of $\lambda^\rightarrow$. For full  $\lambda^\rightarrow$ we show the equivalence of variable containment to an open problem in the theory of PCF;  this equivalence also shows that the problem is decidable in the third order case.

24.11.2022 16:45
Filip Konieczny
Optymalizacja Kombinatoryczna
Factorizing regular graphs
  1. Carsten Thomassen. Factorizing regular graphs. Journal of Combinatorial Theory, Series B. 141, 343-351. (2020).
  2. Filip Konieczny. slides. (2022).
24.11.2022 16:00
Hubert Dej
Optymalizacja Kombinatoryczna
On the Gap Structure of Sequences of Points on a Circle
  1. Lyle Ramshaw. On the gap structure of sequences of points on a circle. Indagationes Mathematicae (Proceedings). 81(1), 527-541. (1978).
  2. Hubert Dej. slides. (2022).
24.11.2022 14:15
Dominik Chmura, Jan Klimczak
Algorytmika
Derandomized Squaring of Graphs

Praca opisuje "zderandomizowany" odpowiednik podnoszenia grafu do kwadratu. Nowa operacja zwiększa spójność grafu (mierzoną jako druga co do wielkości wartość własna macierzy sąsiedztwa) prawie tak dobrze jak potęgowanie grafu, zwiększając stopień grafu nie kwadratowo, a jedynie o stałą. 

Przedstawiono również kilka zastosowań tej konstrukcji, m.in. algorytm alternatywny do wyniku O. Reingolda, który pozwala deterministycznie badać osiągalność w grafach nieskierowanych w logarytmicznej pamięci.

23.11.2022 16:15
Sophie Spirkl
University of Waterloo
Informatyka Teoretyczna
Induced subgraphs and treewidth: H-free graphs

Treewidth is an important measure of the “complexity” of a graph, and as part of the Graph Minors project, Robertson and Seymour characterized unavoidable subgraphs of graphs with large treewidth. Here we are interested in unavoidable induced subgraphs instead. In this context, Lozin and Razgon characterized all finite families F of graphs such that F-free graphs have bounded treewidth. I will talk about related result, characterizing which graphs H have the property that excluding H as well as four families of large treewidth (a complete graph, a complete bipartite graph, all subdivisions of a wall, and their line graphs) as induced subgraphs leads to a class of bounded treewidth.

Joint work with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi

23.11.2022 12:14
Piotr Kubaty
Podstawy Informatyki
Decision Problems for Second-Order Holonomic Recurrences by Eike Neumann, Joel Ouaknine and James Worrel

We study decision problems for sequences which obey a second-order holonomic recurrence of the form

$f (n + 2) = P (n)f (n + 1) + Q(n)f (n)$

with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P . We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f (1), f (2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones.
 

17.11.2022 16:45
Kamil Galewski
Optymalizacja Kombinatoryczna
Majority colorings of sparse digraphs
  1. Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó. Majority Colorings of Sparse Digraphs. Electronic Journal of Combinatorics. 28(2), P2.31. (2021).
  2. Kamil Galewski. slides. (2022).
17.11.2022 16:00
Piotr Kaliciak
Optymalizacja Kombinatoryczna
A counterexample to the lights out problem
  1. János Nagy, Péter Pál Pach. A counterexample to the lights out problem. Journal Graph Theory. 101, 265-273. (2022).
  2. Piotr Kaliciak. slides. (2022).
17.11.2022 14:15
Bartłomiej Błoniarz, Hubert Dej
Algorytmika
More on Change-Making and Related Problems

Mając do dyspozycji zbiór n typów monet o wartościach całkowitych oraz wartość docelową t, w problemie wydawania reszty (change-making) szukamy minimalnej liczby monet, które sumują się do t, zakładając możliwość wykorzystania dowolnej liczby monet każdego typu.

W bardziej ogólnej wersji tego problemu (w wersji all-targets), chcemy obliczyć wyniki dla wszystkich wartości docelowych 0, 1, ..., t. Klasyczny algorytm dynamiczny rozwiązuje ten problem w czasie O(nt).

W publikacji autorzy przedstawiają szereg nowych wyników dotyczących problemu wydawania reszty i innych pokrewnych problemów. Dla u – wartości największej z monet (wagi najcięższego przedmiotu w przypadku problemu plecakowego) pokażemy algorytmy o złożoności:
- Õ(u2+t) dla all-target change-making w oparciu o twierdzenie Erdősa i Grahama dotyczące problemu Frobeniusa;
- Õ(u2+t) dla all-capacities knapsack w oparciu o wcześniejszy algorytm dla change-making;
- Õ(u) dla single-target change-making w oparciu o FFT;
- Õ(nu) dla single-capacity unbounded knapsack, przez wprowadzenie zachłanności umożliwiającej pominięcie obliczania niektórych podproblemów.

16.11.2022 16:15
Hoang La
Jagiellonian
Informatyka Teoretyczna
On Barnette's Conjecture for directed graphs

Knauer and Valicov showed that multiples conjectures from seemingly different problems all fit into the same framework of cuts in matchings of 3-connected cubic graphs. They unite Tait's, Barnette's, and Tutte's conjectures on Hamiltonicity in cubic graphs, Neumann-Lara's on the dichromatic number of planar graphs, and Hochstättler's on contraction of even digraphs. More precisely, these are all equivalent to conjectures of the form ''Every 3-connected, cubic, bipartite/planar/directed graph contains a perfect matching without (directed) cut''. If you drop two of these restrictions (bipartite, planar, directed), then the conjecture is false. If you drop one or none, then the conjecture remains open. We are investigating the dual version of the conjecture with all three restrictions, namely ''Every directed planar Eulerian triangulation can be vertex-partitioned into two acyclic sets''. This new framework can be useful as a planar Eulerian triangulation has an unique partition into three independent sets.

16.11.2022 12:14
Aleksander Katan
Podstawy Informatyki
The combinator M and the Mockingbird lattice by Samuele Giraudo
We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator M. This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule Mx_1 x_1x_1. We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on M and that all connected components of its rewrite graph are Hasse diagram of lattices. This last result is based on the introduction of new lattices on duplicative forests, which are sorts of treelike structures. These lattices are not graded, not self-dual, and not semidistributive. We present some enumerative properties of these lattices like the enumeration of their elements, of the edges of their Hasse diagrams, and of their intervals. These results are derived from formal power series on terms and on duplicative forests endowed with particular operations.
10.11.2022 16:45
Rafał Pyzik
Optymalizacja Kombinatoryczna
Every graph contains a linearly sized induced subgraph with all degrees odd

It was proven by Gallai, that every undirected graph on n vertices contains an induced subgraph on at least n/2 vertices with all degrees even. It is natural to ask a similar question for odd degrees. It was conjectured, that in every graph on n vertices, without isolated vertices, we can find an induced subgraph on at least cn vertices with all degrees odd for some constant c>0. We will prove this conjecture for c=1/10000.

  1. Asaf Ferber, Michael Krivelevich. Every graph contains a linearly sized induced subgraph with all degrees odd. Advances in Mathematics. 406, 108534, (2022).
  2. Rafał Pyzik. slides. (2022).
10.11.2022 16:00
Justyna Jaworska
Optymalizacja Kombinatoryczna
The Lovász Local Lemma is Not About Probability

Since the original statement of Lovas Local Lemma in 1973, multiple variants of the lemma with different levels of complexity have been formulated. We will present a general theorem from which most known variants of LLL follow. Additionally, the results will be generalized to supermodular functions rather than probability measures, allowing a wider range of applications.

  1. Dimitris Achlioptas, Kostas Zampetakis. The Lovász Local Lemma is Not About Probability. arXiv:2111.08837. (2021).
  2. Justyna Jaworska. slides. (2022).
09.11.2022 16:15
Wojciech Czerwiński
University of Warsaw
Informatyka Teoretyczna
Reachability problem in Vector Addition Systems

Recently we managed with co-authors to settle the complexity of the reachability problem for Vector Addition Systems (VASes) to be Ackermann-complete. Despite of that the combinatorics of VASes still remains mysterious and there is a bunch of very natural problems about which we know shockingly little. The focus of my talk will be on tools. I will present techniques, which led to the proof of Ackermann-hardness for the reachability problem and which hopefully may help in solving the remaining challenges.

03.11.2022 16:45
Jędrzej Kula
Optymalizacja Kombinatoryczna
Complete minors and average degree – a short proof

We call graph H a minor of graph G, if there exists such a sequence of deletions of vertices, deletions of edges, or contradictions of edges, which transforms G into H. The authors of the paper created a short proof of the result of Kostochka and of Thomasen. The proven theorem states that for every graph whose vertices have the average degree d the graph itself also contains a complete minor of order Ω(d/sqrt(log(d))).

  1. Noga Alon, Michael Krivelevich, Benny Sudakov. Complete minors and average degree – a short proof. arXiv:2202.08530. (2022).
  2. Jędrzej Kula. Complete minors and average degree – a short proof. slides. (2022).
03.11.2022 16:00
Krzysztof Ziobro
Optymalizacja Kombinatoryczna
Note on the Lamp Lighting Problem

In the most basic version of the Lamp Lighting Problem, we are given an undirected graph G. We can toggle light in a chosen vertex and all of its neighbors. Our goal is to decide if it is possible to turn on the light in all vertices by performing only moves as described. Authors prove that it is always possible and explore other variants of the problem such as the directed case or the problem of checking if all lighting configurations are possible to achieve.

  1. Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand. Note on the lamp lighting problem. arXiv:math/0411201. (2004).
  2. Krzysztof Ziobro. Note on the Lamp Lighting Problem. slides. (2022).
03.11.2022 14:15
Katarzyna Kępińska, Sebastian Spyrzewski
Algorytmika
Fully Dynamic Four-Vertex Subgraph Counting
02.11.2022 16:15
Jędrzej Hodor
Jagiellonian
Informatyka Teoretyczna
Dimension of planar posets

It is a longstanding open problem if posets with a planar cover graph are dim-bounded (meaning that large dimension yields a large standard example as a subposet). This notion is the posets' counterpart of the well-studied χ-boundedness in the graph theory. In my talk, I will focus on summarizing the new progress in this area. The dim-boundedness was recently proved for posests with planar diagram and for posets with planar cover graph and a zero. I will try to sketch some ideas standing behind these results. The other interesting related question in the area is the following. Suppose that a planar poset has a large standard example as a subposet, then, how does this standard example look like? There are two canonical constructions of planar posets with large standard example contained, namely, Kelly's example and Trotter's wheel. We believe that these are (in a structural sense) the only ways to draw a standard example on the plane. For example, we proved that a poset with a planar cover graph, a zero, and large dimension contains a large Trotter's wheel.

The list of coauthors of substantial results that are going to be discussed in my talk: P.Micek, M.Seweryn, H.S.Blake, W.T.Trotter

02.11.2022 12:14
canceled
Podstawy Informatyki
Canceled
27.10.2022 16:00
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
On a Problem of Steinhaus

Let N be a positive integer. A sequence X=(x1,x2,…,xN) of points in the unit interval [0,1) is piercing if {x1,x2,…,xn}∩[i/n,(i+1)/n)≠∅ holds for every n=1,2,…,N and every i=0,1,…,n−1. In 1958 Steinhaus asked whether piercing sequences can be arbitrarily long. A negative answer was provided by Schinzel, who proved that any such sequence may have at most 74 elements. This was later improved to the best possible value of 17 by Warmus, and independently by Berlekamp and Graham. We study a more general variant of piercing sequences. Let f(n)≥n be an infinite nondecreasing sequence of positive integers. A sequence X=(x1,x2,…,xf(N)) is f-piercing if {x1,x2,…,xf(n)}∩[i/n,(i+1)/n)≠∅ holds for every n=1,2,…,N and every i=0,1,…,n−1. A special case of f(n)=n+d, with d a fixed nonnegative integer, was studied by Berlekamp and Graham. They noticed that for each d≥0, the maximum length of any (n+d)-piercing sequence is finite. Expressing this maximum length as s(d)+d, they obtained an exponential upper bound on the function s(d), which was later improved to s(d)=O(d3) by Graham and Levy. Recently, Konyagin proved that 2d⩽s(d)<200d holds for all sufficiently big d. Using a different technique based on the Farey fractions and stick-breaking games, we prove here that the function s(d) satisfies ⌊c1d⌋⩽s(d)⩽c2d+o(d), where c1=ln2/(1−ln2)≈2.25 and c2=(1+ln2)/(1−ln2)≈5.52. We also prove that there exists an infinite f-piercing sequence with f(n)=γn+o(n) if and only if γ≥1/ln2≈1.44. This is joint work with Marcin Anholcer, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Rafał Pyzik, and Mariusz Zając.

  1. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Rafał Pyzik, Mariusz Zając. On a Problem of Steinhaus. arXiv:2111.01887. (2021).
27.10.2022 14:15
Łukasz Selwa, Juliusz Wajgelt
Algorytmika
Token sliding on graphs of girth five

Intuicyjnie problem Token Sliding możemy rozumieć jako grę, w której otrzymujemy graf oraz żetony ustawione na jego wierzchołkach. Pytamy, czy da się uzyskać zadany stan końcowy poprzez przesuwanie żetonów wzdłuż krawędzi grafu tak, że w żadnym momencie dwa żetony nie łączyła wspólna krawędź.

Formalnie mamy na wejściu graf G oraz zbiory niezależne wierzchołków Is, It i chcemy stwierdzić czy istnieje sekwencja I1, …, Is zbiorów niezależnych w G taka, że I1 = Is, Il = It oraz Ii ∆ Ii+1 = {u, v} \in E(G).

Wykazano wcześniej, że dla grafów o talii (ang. girth) 4 lub mniejszej problem Token Sliding jest W[1]-trudny. 

Prezentujemy dowód z pracy „Token sliding on graphs of girth five”, że dla grafów o talii 5 lub większej problem Token Sliding  jest fixed-parameter tractable (FPT).

26.10.2022 16:15
Dömötör Pálvölgyi
Eötvös Loránd University
Informatyka Teoretyczna
At most 3.55^n stable matchings

We improve the upper bound for the maximum possible number of stable matchings among n jobs and n applicants (formerly known as n men and n women) from 131072n to 3.55n. To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Joint work with Cory Palmer

26.10.2022 12:14
Julian Leśniak
Podstawy Informatyki
Tight rank lower bounds for the Sherali–Adams proof system by Stefan Dantchev, Barnaby Martin and Mark Rhodes

We consider a proof (more accurately, refutation) system based on the Sherali–Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s, then we prove that the SA rank of F is k and the SA size of F is  \leq (k + 1)s + 1. We establish that the SA rank of both the Pigeonhole Principle PHP_n^{n-1} and the Least Number Principle LNP_n  is n 2. Since the SA refutation system rank simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS.

20.10.2022 16:00
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
A Note on Generalized Majority Colorings

A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techniques and generalize previously known results on various generalizations of majority coloring. In particular, our unified and simplified approach works for paintability - an online analog of list coloring. This is joint work with Marcin Anholcer, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Mariusz Zając.

  1. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Mariusz Zając. Mrs. Correct and Majority Colorings. arXiv:2207.09739. (2022).
20.10.2022 14:15
Julia Biały, Zofia Glapa
Algorytmika
All Paths Lead to Rome

Roma to łamigłówka rozgrywana na składającej się z kwadratowych pól planszy rozmiaru n x n. Pola pogrupowane są w obszary składające się z co najwyżej 4 sąsiadujących ze sobą komórek, z których każda albo jest wypełniona, albo ma zostać wypełniona strzałką w jednym z 4 kierunków. Celem gry jest wypełnienie wszystkich komórek strzałkami tak by w każdym obszarze była co najwyżej jedna strzałka w danym kierunku i by podążając zgodnie ze strzałkami można było dojść do wyróżnionego pola Roma z każdego pola na planszy.

Autorzy pracy rozważają złożoność obliczeniową gry i pokazują, że uzupełnienie planszy zgodnie z zasadami jest problemem NP-zupełnym, zliczenie możliwych rozwiązań jest #P zupełne oraz wyznaczenie liczby zadanych z góry strzałek koniecznych by gra miała tylko jedno rozwiązanie jest ΣP2 - zupełne.

Praca dowodzi też, że zakładając prawdziwość ETH problem uzupełnienia planszy dla danej instancji gry nie może być rozwiązany w czasie O(2o(n)). Omawia także algorytm programowania dynamicznego rozwiązujący planszę gry, opierający się na strukturach Catalana.

19.10.2022 16:15
Vida Dujmović
University of Ottawa
Informatyka Teoretyczna
Stack and Queue layouts

This talk will focus on two graph parameters: stack layouts (aka. book embeddings) and queue layouts of graphs. I will talk about the history of these two graph parameters, their  still not fully understood relationship and some recent breakthroughs.

19.10.2022 12:14
Juliusz Wajgelt
Podstawy Informatyki
Short Proofs of Normalization for the simply-typed λ-calculus, permutative conversions and Godel’s T by Felix Joachimski and Ralph Matthes
Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style `a la Tait and Girard. It
is also shown that the extension of the system with permutative conversions by (\eta) rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of “immediate simplification”. By introducing an infinitely branching inductive rule the method even extends to Godel’s T
13.10.2022 16:00
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget

We study the problem of coloring a unit interval graph that changes dynamically. In our model the unit intervals are added or removed one at a time and have to be colored immediately so that no two overlapping intervals share the same color. After each update, only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper, we show, that if the graph remains k-colorable at all times, and the updates consist of insertions only, then we can achieve the amortized recourse budget of O(k7logn) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bosek et al., Recoloring Interval Graphs with Limited Recourse Budget. SWAT 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As a byproduct of independent interest, we include a new result on coloring proper circular-arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs A. We show that if there is a set A′ of non-intersecting unit arcs of size L2−1 such that A∪A′ does not contain L+1 arcs intersecting in one point, then it is possible to color A with L colors. This complements the work on unit circular arc coloring, which specifies sufficient conditions needed to color A with L+1 colors or more. This is joint work with Anna Zych-Pawlewicz.

  1. Bartłomiej Bosek, Anna Zych-Pawlewicz. Recoloring Unit Interval Graphs with Logarithmic Recourse Budget. arXiv:2202.08006. (2022).
12.10.2022 16:15
Friedrich Eisenbrand
École Polytechnique Fédérale de Lausanne
Informatyka Teoretyczna
Integer programming with few constraints

The talk features a survey as well as recent new results on two independent approaches to derive efficient algorithms for integer programming, namely algorithms based on the geometry of numbers and dynamic programming techniques, with an extra spotlight on the case in which the number of constraints (apart from bounds on the variables) is small. We will highlight open problems and possible future directions.

The presented  results of the speaker have been jointly achieved with Daniel Dadush, Thomas Rithvoss and Robert Weismantel.

12.10.2022 12:14
Mateusz Olszewski
Podstawy Informatyki
Implicit computation complexity in higher-order programming languages (A Survey in Memory of Martin Hofmann) by Ugo Dal Lago
This paper is meant to be a survey about implicit characterizations of complexity classes by fragments of higher-order programming languages, with a special focus on type systems and subsystems of linear logic. Particular emphasis will be put on Martin Hofmann’s contributions to the subject, which very much helped in shaping the field.
06.10.2022 16:00
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Dimension of planar posets

It is a long-standing open problem if planar posets are dim-bounded (an analog of chi-bounded in the graph theory). I summarize recent progress on this problem. We explore different notions of what does it mean for posets to be planar. Finally, I will sketch the proof of dim-boundedness in the case of posets with planar cover graphs and a zero.

  1. Piotr Micek, Heather C. Smith Blake, William T. Trotter. Boolean dimension and dim-boundedness: Planar cover graph with a zero. arXiv:2206.06942. (2022).
  2. Jędrzej Hodor. Dimension of planar posets. slides. (2022).
05.10.2022 16:15
Paul Seymour
Princeton University
Informatyka Teoretyczna
Getting closer to the Erdős-Hajnal conjecture
A general n-vertex graph may not have a clique or stable set larger than O(log n), but excluding an induced subgraph makes a significant difference. The Erdős-Hajnal conjecture (from 1977) says that for every graph H, there exists c such that every H-free graph G (that is, not containing H as an induced subgraph) has a clique or stable set of size at least |G|c. This is still open, and is notoriously intractable.


Erdős and Hajnal proved a general bound: for every H there exists c>0 such that every H-free graph has a clique or stable set of size at least exp(c (log|G|)1/2). This is still the record for most graphs H, but in some instances one can do better. Let us say H is "friendly" if there exists c>0 such that every H-free graph G has a clique or stable set of size at least exp(c (log|G| loglog|G|)1/2). We prove that many graphs are friendly – for instance, all split graphs are friendly, and so is the eight-vertex path, and all graphs obtained from a cograph by adding a new vertex joined arbitrarily.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott

15.06.2022 16:15
Piotr Micek
Jagiellonian
Informatyka Teoretyczna
Boolean dimension and dim-boundedness of posets with a unique minimal element whose cover graphs are planar

In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension?  We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most 13. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of O(log n) bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with O(log2n) bits [Thorup, JACM 2004], and it remains open to determine whether a scheme using labels with O(log n) bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.

Within this talk after a quick introduction, I aim to lay out all the ideas behind the proof bounding Boolean dimension.

This is a joint work with Heather Smith Blake and Tom Trotter.

09.06.2022 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
The 1/3 - 2/3 conjecture

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.

08.06.2022 16:15
Michał Wrona
Jagiellonian
Informatyka Teoretyczna
Local consistency methods in Solving CSPs and CSP-like problems over omega-categorical structures

Feder-Vardi conjecture has been settled independently by Dmitriy Zhuk and Andrei Bulatov. What is perhaps even more interesting, though, is that they not only confirmed the complexity (Feder-Vardi) conjecture, i.e., CSP(B) for a finite structure B is either in P or it is NP-complete, but they also confirmed the algebraic dichotomy conjecture describing  tractable B in terms of operations preserving B.

A similar algebraic dichotomy conjecture called an infinite algebraic dichotomy conjecture has been established for CSP(B) over first-order reducts B of finitely bounded homogeneous structures, all of which are in particular omega-categorical. Despite recent advances towards solving this dichotomy, it still seems to be wide open. One of the reasons is probably that local consistency  and similar algorithmic techniques are in this context not yet fully understood. This step seems to be crucial since the characterization of finite-domain CSP solvable by local consistency  is considered as a major step towards the resolution of the dichotomy.

In this talk, I will survey the results on the local consistency methods in solving CSP and CSP-like problems over omega-categorical structures.

08.06.2022 12:15
Karolina Gontarek
Podstawy Informatyki
THE TU–DENG CONJECTURE HOLDS ALMOST SURELY by LUKAS SPIEGELHOFER AND MICHAEL WALLNER

The Tu–Deng Conjecture is concerned with the sum of digits w(n) of n in base 2 (the Hamming weight of the binary expansion of n) and states the following: assume that k is a positive integer and t \in  {1, . . . , 2^k 2}. Then

#\{ (a, b) {0, . . . , 2k 2}^2 : a + b t mod 2^k 1, w(a) + w(b) < k \ \leq 2^{k-1}


We prove that the Tu–Deng Conjecture holds almost surely in the following sense: the proportion of t \in {1, . . . , 2^k 2} such that the above inequality holds approaches 1 as k tends to infinity. Moreover, we prove that the Tu–Deng Conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of n and n + t.

02.06.2022 17:00
Krzysztof Pióro
Optymalizacja Kombinatoryczna
Brooks' Theorem via the Alon-Tarsi Theorem

Brooks' Theorem states that every connected graph G with maximum degree d is d-colorable unless G is an odd cycle or a complete graph. It is one of the most famous theorem on graph colorings. In the paper, the author presents yet another proof of this theorem. This proof is based on Alon-Tarsi Theorem and it remains valid in a more general choosability version of Brooks' theorem.

  1. Jan Hladký, Daniel Král’, Uwe Schauz. Brooks’ Theorem via the Alon–Tarsi Theorem. Discrete Mathematics. 310 (23), 3426-3428. (2010).
  2. Krzysztof Pióro. Brooks’ Theorem via the Alon-Tarsi Theorem. slides. (2022).
02.06.2022 16:15
Demian Banakh
Optymalizacja Kombinatoryczna
Separating polynomial χ-boundedness from χ-boundedness

A class of graphs is hereditary χ-bounded if it is closed under taking induced subgraphs and every graph’s chromatic number is bounded by some function of its clique number. A well-known recently stated open question has been whether for every hereditary χ-bounded class that function can be chosen to be a polynomial. We provide a counterexample for it; namely, for any function f, we construct a hereditary χ-bounded class containing graphs of large chromatic number. In particular, for any polynomial f, such a class exists, which answers the aforementioned question negatively.

  1. Marcin Briański, James Davies, Bartosz Walczak. Separating polynomial χ-boundedness from χ-boundedness. arXiv:2201.08814. (2022).
  2. Demian Banakh. Separating polynomial χ-boundedness from χ-boundedness. slides. (2022).
02.06.2022 14:15
Jędrzej Kula, Maciej Nemś
Algorytmika
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Grafy przecięć geometrycznych to grafy, gdzie wierzchołki odpowiadają figurom geometrycznym w d-wymiarowej przestrzeni euklidesowej. Mogą do to być na przykład kule, kwadraty, hiperkostki. Krawędź między dwoma wierzchołkami istnieje, jeśli dwie figury przecinają się. Jest to typowy sposób modelowania na przykład komunikacji bezprzewodowej.

W pracy autorzy zajmują się obliczaniem średnicy tego typu grafów. Dokładniej rozważają to, czy da się ten problem rozwiązać w czasie poniżej kwadratowym względem liczby wierzchołków. Na referacie zostanie pokazany dowód algorytmu o czasie działania O(n logn) dla sprawdzania, czy średnica jest mniejsza bądź równa 2 dla grafów przecięć kwadratów jednostkowych równoległych do osi. Następnie zostanie pokazane dolne ograniczenie szukania średnicy dla kul jednostkowych na bazie Orthogonal Vectors Hypothesis. Ograniczenie to pokazuje, że nie ma algorytmów pod kwadratowych przy założeniu Orthogonal Vectors Hypothesis.

01.06.2022 12:15
Juliusz Wajgelt
Podstawy Informatyki
EFFICIENT FULL HIGHER-ORDER UNIFICATION by PETAR VUKMIROVIC, ALEXANDER BENTKAMP, AND VISA NUMMELIN
We developed a procedure to enumerate complete sets of higher-order unifiers based on work by Jensen and Pietrzykowski. Our procedure removes many redundant unifiers by carefully restricting the search space and tightly integrating decision procedures for fragments that admit a nite complete set of uni ers. We identify a new such fragment and describe a procedure for computing its uni ers. Our uni cation procedure, together with new higher-order term indexing data structures, is implemented in the Zipperposition theorem prover. Experimental evaluation shows a clear advantage over Jensen and Pietrzykowski's procedure.
26.05.2022 17:00
Bartosz Podkanowicz
Optymalizacja Kombinatoryczna
Digraphs are 2-weight choosable

Consider following problem. We are given a digraph. For every edge, there are 2 options to choose a weight for this edge. We want to pick the weights of edges in a specific way. After picking weights we color vertices. The color of the vertex will be the sum of incoming edges minus the sum of outgoing edges from that vertex. We show that it is always possible to choose weights of edges such that the resulting coloring will be proper. This property is called 2-weight-choosability.

  1. Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, Brett Stevens. Digraphs are 2-Weight Choosable. Electronic Journal of Combinatorics. 18(1), P21. (2011).
  2. Bartosz Podkanowicz. Digraphs are 2-weight choosable. slides. (2022).
26.05.2022 16:15
Łukasz Selwa
Optymalizacja Kombinatoryczna
A better lower bound on average degree of 4-list-critical graphs

A graph G is k-list-critical if it is not (k-1)-choosable, but every proper subgraph of G is (k-1)-choosable. We give a new lower bound for the average degree of incomplete k-list-critical graphs and online k-list-critical graphs. The presented bound improves the earlier known lower bounds for k = 4,5,6.

  1. Hal Kierstead, Landon Rabern. Extracting list colorings from large independent sets. arXiv:1512.08130. (2015).
  2. Landon Rabern. A better lower bound on average degree of 4-list-critical graphs. arXiv:1602.08532. (2016).
  3. Łukasz Selwa. A better lower bound on average degree of 4-list-critical graphs. slides. (2022).
26.05.2022 14:15
Grzegorz Gawryał, Rafał Kilar
Algorytmika
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
25.05.2022 16:15
Szymon Toruńczyk
University of Warsaw
Informatyka Teoretyczna
Ordered graphs of bounded twin-width and monadically NIP graph classes

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.

This has several consequences.First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.

Those results are joint work with Bonnet, Giocanti, Ossona de Mendez, Simon, Thomasse, accepted to STOC'22.

Time permitting, I will also discuss the more general landscape of monadically NIP graph classes, generalizing both nowhere dense classes and classes of bounded twin-width.

25.05.2022 12:15
Vitaliy Mysak
Podstawy Informatyki
An Introduction to the Clocked Lambda Calculus byJörg Endrullis, Dimitri Hendriks, Jan Willem Klop, and Andrew Polonsky
We give a brief introduction to the clocked λ-calculus, an extension of the classical λ-calculus with a unary symbol τ used to witness the β-steps. In contrast to the classical λ-calculus, this extension is infinitary strongly normalising and infinitary confluent. The infinitary normal forms are enriched Lévy–Longo Trees, which we call clocked Lévy–Longo Trees.
19.05.2022 17:00
Rafał Kilar
Optymalizacja Kombinatoryczna
Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation

An online chain partitioning algorithm is presented with one element of a poset at a time and has to assign it to a chain, partitioning the poset. We consider posets with elements represented by unit length intervals. The paper slightly improves the lower bound for the minimum number of chains needed by an online algorithm to partition these posets from ⌊3/2 w⌋ to ⌈3/2 w⌉.

  1. Csaba Biró, Israel R. Curbelo. Improved lower bound on the on-line chain partitioning of semi-orders with representation. arXiv:2111.04790. (2021).
  2. Rafał Kilar. Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation. slides. (2022).
19.05.2022 16:15
Krzysztof Potępa
Optymalizacja Kombinatoryczna
Unit-Monge matrices and seaweed braids

Simple unit-Monge matrices form a special subclass of square matrices, which can be represented implicitly in linear space by permutations. Somewhat surprisingly, the subclass is closed under distance multiplication. We will show connection between simple unit-Monge matrices and seaweed braids: braids in which each pair of strings crosses at most once. In particular, distance multiplication is equivalent to a "combing procedure", where double-crossings in braid are removed. We will discuss applications of these methods to a few subsequence problems. In particular, the combing procedure can be exploited to obtain an elegant algorithm for all-substring LCS problem.

  1. Alexander Tiskin. Semi-local string comparison: algorithmic techniques and applications. arXiv:0707.3619. (2007).
  2. Krzysztof Potępa. Unit-Monge matrices and seaweed braids. slides. (2022).
19.05.2022 14:15
Andrii Orap, Maksym Zub
Algorytmika
Grundy Distinguishes Treewidth from Pathwidth

Strukturalne parametry grafów, takie jak treewidth, pathwidth i clique-width, są głównym tematem badań sparametryzowanej złożoności. Głównym celem badań w tej dziedzinie jest zrozumienie „ceny ogólności” tych szerokości: kiedy przechodzimy od pojęć bardziej restrykcyjnych do bardziej ogólnych, jakie są problemy, w których złożoność pogarsza się z fixed-parameter tractable do intractable? Ten rodzaj pytania jest już bardzo dobrze zbadany, ale, co jest dość uderzające, algorytmiczna granica między dwoma (prawdopodobnie) najbardziej centralnymi pojęciami szerokości (notacjami), treewidth i pathwidth, jest nadal niezrozumiała: obecnie nie jest znany żaden naturalny problem na grafie, który byłby W-trudny dla jednego, ale FPT dla drugiego. Rzeczywiście, zaskakującym rozwojem ostatnich kilku lat była obserwacja, że: w przypadku wielu najbardziej paradygmatycznych problemów ich złożoność dla tych dwóch parametrów w rzeczywistości dokładnie się pokrywają, pomimo faktu, że szerokość drzewa jest parametrem o wiele bardziej ogólnym. W ten sposób wydaje się, że dodatkowa ogólność szerokości drzewa nad szerokością ścieżki często przychodzi „za darmo”.

Naszym głównym wkładem w ten artykuł jest odkrycie pierwszego naturalnego przykładu, w którym ta ogólność ma wysoką cenę. Rozważamy Grundy Coloring, wariację kolorowania, w której próbujemy obliczyć najgorsze możliwe kolorowanie, które można przypisać do grafu przez zachłanny algorytm First-Fit . Pokazujemy, że ten dobrze zbadany problem jest parametryzowany (FPT) przez pathwidth; jednakże to staje się znacznie trudniejsze (W[1]-hard), gdy jest sparametryzowany przez treewidth. Ponadto pokazujemy, że Grundy Coloring sprawia, że jest drugi skok złożoności dla bardziej ogólnych szerokości, gdy staje się para-NP-hard dla clique-width. Dlatego Grundy Coloring ładnie oddaje złożoność kompromisów między trzema najlepiej zbadanymi parametrami. Uzupełniając obraz, pokazujemy, że Grundy Coloring jest parametryzowane przez FPT według modular-width.

18.05.2022 16:15
Rose McCarty
University of Warsaw
Informatyka Teoretyczna
Circuit decompositions of group-labelled graphs

This talk focuses on Eulerian graphs whose arcs are directed and labelled in a group. Each circuit yields a word over the group, and a circuit is non-zero if this word does not evaluate to 0. We give a precise min-max theorem for the following problem. Given a vertex v, what is the maximum number of non-zero circuits in a circuit-decomposition where each circuit begins and ends at v?

This is joint work with Jim Geelen and Paul Wollan. Our main motivation is a surprising connection with vertex-minors which is due to Bouchet and Kotzig.

18.05.2022 12:15
Jan Koscisz
Podstawy Informatyki
Functions-as-constructors higher-order unification: extended pattern unification by Tomer Libal and Dale Miller
Unification is a central operation in constructing a range of computational logic systems based on first-order and higher-order logics. First-order unification has several properties that guide its incorporation in such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-called pattern subset of higher-order unification was designed to be a small extension to first-order unification that respects the laws governing λ-binding (i.e., the equalities for α, β, and η-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been used in numerous implemented systems and in various theoretical settings, it is too weak for many applications. This paper defines an extension of pattern unification that should make it more generally applicable, especially in proof assistants that allow for higher-order functions. This extension’s main idea is that the arguments to a higher-order, free variable can be more than just distinct bound variables. In particular, such arguments can be terms constructed from (sufficient numbers of) such bound variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.