Seminars
02.03.2023 16:15 
Theoretical computer science TBA  03.02 
Poprzednie referaty
26.01.2023 16:45 Krzysztof Barański 
Combinatorial Optimization A note on polynomials and ffactors of graphs 

26.01.2023 16:00 Demian Banakh 
Combinatorial Optimization Token sliding on graphs of girth five 
In the Token sliding problem, one starts with a graph and independent sets I_{s}, I_{t}. We put k tokens on vertices of I_{s} and ask whether it's possible to reach I_{t} after a finite sequence of moves, where 1 move is sliding 1 token along the edge so that no 2 tokens are adjacent at any point. It was shown in 2021 that this problem is W[1]hard for graphs of girth 4 or less. In this presentation, we will see how the problem becomes Fixedparameter tractable for the other graphs (girth 5 or more). 
26.01.2023 14:15 Grzegorz Gawryał, Szymon Salabura 
Algorytmika TSP in a Simple Polygon 
Problem komiwojażera (TSP) jest jednym z najbardziej popularnych problemów optymalizacyjnych w algorytmice. Jest on NPtrudny, nawet wtedy, gdy graf na wejściu jest grafem odległości euklidesowych między danymi punktami na płaszczyźnie. Autorzy wprowadzają nowy wariant tego problemu  TSP w wielokącie prostym, w którym to problemie należy znaleźć najkrótszą trasę nie wychodzącą poza wielokąt i odwiedzającą pewien zbiór punktów w tym wielokącie, w dowolnej kolejności. Autorzy najpierw pokazują, jak zastosować ogólniejszy i dość skomplikowany algorytm Marxa, Pilipczuka i Pilipczuka do tego problemu, uzyskując złożoność poly(n,m) + 2^{(O(sqrt(n) log n))}, a następnie prezentują własny, znacznie prostszy algorytm rozwiązujący ten wariant TSP w tej samej złożoności. 
25.01.2023 16:15 Andrzej Grzesik Jagiellonian 
Theoretical computer science Turántype problems for directed cycles 
A standard Turán problem for a graph F is to determine the maximal number of edges in a graph not containing F as a subgraph. This problem for directed cycles in oriented graphs is trivial, but its various generalizations, when one asks for minimum outdegree or number of other subgraphs, occurred to be hard problems. In particular, finding minimum outdegree (or semidegree) forcing an oriented graph to contain a directed triangle is a CaccettaHäggkvist conjecture, which is open for 45 years despite numerous partial results. During the talk we will present a solution (obtained with Jan Volec) to a conjecture of Kelly, Kühn and Osthus on the minimum semidegree forcing an oriented graph to contain a directed cycle of any given length at least four. We will also discuss results (obtained jointly with Justyna Jaworska, Bartłomiej Kielak and Tomasz Ślusarczyk) for the generalized Turán problem for directed cycles when one maximizes the number of directed cycles of some other length. 
25.01.2023 12:14 Krzysztof Barański 
Computer science foundations A verified framework for higherorder 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, multipleargument functions, while preserving the ability to evaluate partial applications. Firstorder 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 higherorder functions (where uncurrying can also be performed on parameters and results of higherorder functions) is challenging. This article develops a generic framework that expresses higherorder uncurrying optimizations as typedirected insertion of coercions, and prove its correctness. The proof uses stepindexed logical relations and was entirely mechanized using the Coq proof assistant. 
19.01.2023 16:45 Bartłomiej Błoniarz 
Combinatorial Optimization A Survey of the Game “Lights Out!" 

19.01.2023 16:00 Jakub Dziarkowski 
Combinatorial Optimization Note on Perfect Forests 

19.01.2023 14:15 Bartłomiej Wacławik, Krzysztof Ziobro 
Algorytmika Tiny Pointers 
Praca wprowadza nowe pojęcie: wskaźniczek. Wskaźniczek jest obiektem, który pozwala na dostęp do jednego z n miejsc w pamięci, jednocześnie używając znacząco mniej niż log(n) bitów. Jest to możliwe dzięki użyciu wprowadzonej w pracy tablicy dereferencyjnej, która pozwala dla danego klucza k (z dużym prawdopodobieństwem) zaalokować komórkę pamięci zwracając wskaźniczek, który razem z kluczem pozwalaja uzyskać dostęp do zaalokowanej komórki w czasie stałym. Dodatkowo autorzy podają przykłady zastosowań w popularnych strukturach danych, których rozmiar można zredukować dzięki zastąpieniu klasycznych wskaźników wskaźniczkami. Wśród tych przykładów znajdują się między innymi drzewa BST oraz słowniki o stałej pojemności. 
18.01.2023 16:15 Tuukka Korhonen University of Bergen 
Theoretical computer science An improved parameterized algorithm for treewidth 
Treewidth is a fundamental graph parameter that, informally, characterizes how treelike a graph is. We give a 2^{O(k^2)}·n^{O(1)} time algorithm for determining if the treewidth of a given nvertex graph is at most k and outputting the corresponding tree decomposition. This resolves the longstanding open problem of whether there is a 2^{o(k^3)}·n^{O(1)} time algorithm for treewidth. In particular, this is the first improvement on the dependency on k in fixedparameter algorithms for treewidth since the 2^{O(k^3)}·n^{O(1)} time algorithm given in 1991 by Bodlaender and Kloks, and independently, by Lagergren and Arnborg. We also give a k^{O(k/ε)}·n^{O(1)} time (1+ε)approximation algorithm for treewidth. Joint work with Daniel Lokshtanov. 
18.01.2023 12:14 Roman Madej 
Computer science foundations 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 wellknown 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’.

12.01.2023 16:45 Julia Biały 
Combinatorial Optimization Can a party represent its constituency? 
The paper focuses on the representation problem in political elections, using a theorem from number theory. A. Katz's work gives an answer to the question  of whether there exists a way to construct the election list so that it does not matter how many politicians are selected and the politically different groups of the party will be represented?

12.01.2023 16:00 Katzper Michno 
Combinatorial Optimization Internal Partitions of Regular Graphs 
We consider internal partitions of graphs, which is a partition of V into two sets, such that every vertex has at least half of its neighbors in its own set. Several investigators have raised the conjecture that dregular graphs always have an internal partition, assuming their set of vertices is big enough. Here we prove this conjecture for d=6. We also investigate the case when V=d+4, which leads to some new problems on cubic graphs, and find new families of graphs that don't have an internal partition.

12.01.2023 14:15 Ignacy Buczek, Tomasz Buczyński 
Algorytmika List Colouring Trees in Logarithmic Space 
Dla danego nwierzchołkowego grafu G = (V, E) oraz listy L(v) ⊆ {1, ..., n} dozwolonych kolorów dla każdego wierzchołka v ∊ V, kolorowanie listowe jest kolorowaniem wierzchołkowym c grafu G spełniającym c(v) ∊ L(v) dla każdego v. Autorzy pracy dowodzą, że problem kolorowania listowego nwierzchołkowych drzew może być rozwiązany za pomocą deterministycznej maszyny Turinga używającej O(log n) bitów na taśmie roboczej. 
11.01.2023 16:15 Jonathan Narboni Jagiellonian 
Theoretical computer science Vizing's Conjecture Holds 
In 1964 Vizing proved that to properly color the edges of a graph G, one need at most ∆+1 colors, where ∆ is the maximum degree of G. In his paper, Vizing actually proves that one can transform any proper edge coloring into a (∆+1)edgecoloring using only Kempe changes. Soon after his paper, he asked the following question: is an optimal edgecoloring always reachable from any proper edgecoloring using only Kempe changes? Bonamy & al. proved that the conjecture holds for triangle free graphs, following their work, we prove that it holds for all graphs. 
11.01.2023 12:14 Rafał Loska 
Computer science foundations 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 wellknown 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. 
05.01.2023 16:45 Jakub Siuta 
Combinatorial Optimization On Induced Subgraphs with All Degrees Odd 
Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs.

05.01.2023 16:00 Aleksander Katan 
Combinatorial Optimization A generalization of Konig's theorem 
König's theorem lets us determine the maximum number of pairwise independent edges in a bipartite graph. In the paper, L. Lovász focuses on critical graphs, meaning that if any of their edges are removed, the size of maximum matching diminishes. Considering a certain generalization of the abovementioned concept, Lovász gives a simple condition that is necessary and sufficient for a graph to be critical. The result is used to solve a conjecture by Erdős regarding strict hypergraph coloring. 
04.01.2023 16:15 Michał Pilipczuk University of Warsaw 
Theoretical computer science Flipper games for monadically stable classes of graphs 
We will provide a gentle introduction to the ongoing work on constructing a structural theory for graph classes defined by forbidding obstructions definable in logic. The focus will be on monadically stable classes of graphs: classes where one cannot define arbitrary long total orders using a fixed firstorder formula. We will review recent advances on characterizing these classes in a purely combinatorial manner, in particular through a game model: the Flipper game. 
04.01.2023 12:14 Sebastain Spyrzewski 
Computer science foundations A characterization of lambdaterms 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 ktuple, and returns the ith number in the tuple (we do not require that, using λcalculus, one can construct the representation of the ktuple 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. 
22.12.2022 16:45 Ignacy Buczek 
Combinatorial Optimization K4free graphs have sparse halves 
In the extremal graph theory, there are many unsolved problems related to the finding of sparse subsets in graphs. The most famous one, stated by Erdos in 1976, asks whether every trianglefree graph contains n/2 vertices that span at most 1/50 n^{2} edges. In our work we consider, and successfully prove, a modified version of this theorem which conjectures that every K_{4}free graph has n/2 vertices spanning at most 1/18 n^{2} edges. This bound is tight, as the balanced blowup of a triangle is an extreme example. We achieve the proof by strengthening some of the previous results and by stating some new arguments which show that the only K_{4}free graph which has at least 1/18 n^{2} edges in every half is the blowup of a triangle. 
22.12.2022 16:00 Łukasz Selwa 
Combinatorial Optimization Isomorphic bisections of cubic graphs 
Ando conjecture states that we can partition vertices of any cubic graph into two parts that induce isomorphic subgraphs. We show that this conjecture is true for sufficiently large connected cubic graphs. In the proof, we use probabilistic methods with recoloring arguments. 
22.12.2022 14:15 Kamil Galewski, Piotr Kaliciak 
Algorytmika Lower Bounds on Retroactive Data Structures 
21.12.2022 16:15 Ross Kang University of Amsterdam 
Theoretical computer science Colouring graphs with sparse neighbourhoods 
Let us say that a graph of maximum degree Δ has local density at most η if the number of edges spanning any neighbourhood is at most η·(Δ choose 2), i.e. if the edge density is no more than an η fraction of the maximum possible. What is the largest chromatic number of such graphs? When η=0, this corresponds to asking about the largest chromatic number in trianglefree graphs of maximum degree Δ. This goes back to an old question of Vizing and is the objective of a recent breakthrough of Molloy. It is natural — and also connects to various other problems in the field — to consider other choices for η. We will broadly discuss this problem, including its classic origins in Ramsey theory, and some different ideas that have recently proven fruitful. This will touch on recent joint works with Davies, Hurley, de Joannis de Verclos, Pirot, and Sereni.

21.12.2022 12:14 Łukasz Grobelczyk  canceled 
Computer science foundations Bijections between planar maps and planar linear normal \lambdaterms with connectivity condition by Wenjie Fang 
15.12.2022 16:45 Hubert Zięba 
Combinatorial Optimization The 3flow conjecture, factors modulo k, and the 123conjecture 
The 123 conjecture asserts that for every connected simple graph of order at least 3 edges can be weighted with 1,2 and 3 so that each pair of adjacent has different weighted degrees. We consider a modified version of this conjecture with 1,2 weights only. By using ffactors modulo k of the graph, we prove it for nonbipartite (6𝛘(G)5)edgeconnected graphs and completely characterize bipartite graphs having this property. 
15.12.2022 16:00 Tomasz Mazur 
Combinatorial Optimization Improved lower bound for the list chromatic number of graphs with no Kt minor 
Hadwiger's conjecture is an important conjecture in graph theory which states that every graph without a K_{t}minor is (t1)colorable. This conjecture does not extend to list colorings, but Kawarabayashi and Mohar (2007) conjectured that there exists a constant c such that every graph with no K_{t}minor has a list chromatic number at most c·t. More specifically, they conjectured that c = 3/2 is sufficient. Refuting the latter conjecture, we prove using the probabilistic method that there exist graphs with no K_{t}minor with list chromatic number at least (2o(1))·t, and hence c ≥ 2 is necessary. This improves the previous bestknown lower bound by Barát, Joret, and Wood (2011), who proved that c ≥ 4/3. 
15.12.2022 14:15 Roman Madej, Paweł Nowak 
Algorytmika Sinkless Orientation Made Simple 
Sinkless Orientation jest problemem grafowym, polegającym na skierowaniu krawędzi w grafie, aby każdy wierzchołek o stopniu co najmniej trzy miał krawędź wychodzącą. Problem ten odgrywa kluczową rolę w zrozumieniu teorii obliczeń rozproszonych. Tematem rozważań pracy będzie analiza lokalności problemu, jednej z podstawowej własności rozproszonych algorytmów grafowych, w modelach LOCAL i SLOCAL. Znane jest już dokładne ograniczanie w modelu LOCAL oraz ograniczenie górne w modelu SLOCAL, natomiast standardowe dowody wykorzystują zaawansowane techniki. W pracy autorzy prezentują jednak nowe, elementarne i samowystarczalne dowody obydwu ograniczeń. 
14.12.2022 16:15 Boris Bukh Carnegie Mellon 
Theoretical computer science Extremal graphs without exponentiallysmall bicliques 
In 1954 Kővári, Sós, and Turán showed that every nvertex graph not containing K_{s,t} has at most O(n^{2−1/s}) edges. We construct graphs matching this bound with t≈9^{s}, improving on factorialtype bounds. In this talk, I will explain probabilistic and geometric ideas behind the construction. 
14.12.2022 12:14 Filip Jasiński 
Computer science foundations 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. 
08.12.2022 16:45 Grzegorz Gawryał 
Combinatorial Optimization On topological aspects of orientations 
Constrained graph orientation problem deals with directing graph edges such that graph vertices fulfills some conditions. Here, we are focusing on contant indegree orientations of maximal planar and similar classes of graphs. We analyse the relationship between such orientations and other combinatorial properties of these graphs, including the existence of particular decompositions into trees given by the famous Nash William's theorem. 
08.12.2022 16:00 Rafał Kilar 
Combinatorial Optimization Minimal NonTwoColorable Hypergraphs and Minimal Unsatisfiable Formulas 
It is known that the number of edges in a minimal non2colorable hypergraph is at least as high as the number of its vertices. We show the link between this and the fact that a minimal unsatisfiable CNF formula with n variables must contain at least n + 1 clauses. We show different proof of these facts and give infinite versions. We also analyze the structure of minimal unsatisfiable CNF formulas with exactly n variables and n + 1 clauses. 
07.12.2022 16:15 László Végh London School of Economics 
Theoretical computer science Interior point methods are not (much) worse than Simplex 
Whereas interior point methods provide polynomialtime linear programming algorithms, the running time bounds depend on bitcomplexity 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 polynomialtime pathfollowing interior point method where the number of iterations also admits a combinatorial upper bound O(2^{n} n^{1.5} log n) for an nvariable 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 pathfollowing method must take exponentially many iterations. The number of iterations of our algorithm is at most O(n^{1.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 pathfollowing interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewiselinear 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). 
07.12.2022 12:14 Katarzyna Król 
Computer science foundations 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))n≥0 and decides whether u(n) = 0 for some n ∈ S . The main technical contribution of the paper is to exhibit such a set 
01.12.2022 16:45 Szymon Salabura 
Combinatorial Optimization Farey sequence and Graham’s conjectures 
The Farey sequence F_{n} is the set of rational numbers a/b with 0 ≤ a ≤ b ≤ n and gcd(a,b) = 1. In 1970, Graham proposed the following conjecture. Let a_{1}, a_{2}, ..., a_{n} be distinct positive integers. There exist indices i ≠ j, such that we have a_{i}/gcd(a_{i},a_{j}) ≥ n. In the paper, the authors show interesting properties of Farey sequence sets and how they are closely related to Graham's problems. 
01.12.2022 16:00 Katarzyna Kępińska 
Combinatorial Optimization ColorCritical Graphs on a Fixed Surface 
A graph G is kcolorcritical if G is not (k1)colorable, but every proper subgraph is. For S, an orientable surface other than the sphere, there are infinitely many kcolorcritical graphs if and only if 2<k<6. For k>4 there is the polynomial algorithm for deciding if a graph can be colored with k colors. In this paper, the authors prove those theorems and show some results for list coloring. 
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 online 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 
Theoretical computer science Modularity of minorfree graphs 
Modularity is a wellestablished 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 modularitybased 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 
Computer science foundations 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 nstep 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 
Combinatorial Optimization Factorizing regular graphs 
A qfactor of a kregular graph is its qregular subgraph covering all vertices. qfactorization is a partition of edges of a graph into disjoint qfactors. For qfactorization to exist it is necessary that q\mid k. It was proven that for even q the converse is also true  qdregular graph has a qfactorization. The paper investigates when qdregular graph with odd q admits qfactorization, given additional assumptions like planarity and/or high connectivity. 
24.11.2022 16:00 Hubert Dej 
Combinatorial Optimization On the Gap Structure of Sequences of Points on a Circle 
The problem of determining a sequence of points on the unit circle is considered, such that at any time t the lengths of the segments (sticks) resulting from splitting the circle at the locations set by the first t points are as equal as possible. The authors consider the sequence x_{k}=lg(2k1) mod 1 discovered and analyzed by De Brujin and Erdos in 1949 called the log stickbreaking strategy, proven to be optimal under 3 selected measures. The analysis of this sequence is extended by showing an interpretation in which log stickbreaking is a uniquely optimal strategy, and a more general framework is designed in which the optimality of this strategy can be explored. 
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 
Theoretical computer science Induced subgraphs and treewidth: Hfree 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 Ffree 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 
Computer science foundations Decision Problems for SecondOrder Holonomic Recurrences by Eike Neumann, Joel Ouaknine and James Worrel 
We study decision problems for sequences which obey a secondorder holonomic recurrence of the form $f (n + 2) = P (n)f (n + 1) + Q(n)f (n)$ with rational polynomial coefficients, where P is nonconstant, Q is nonzero, 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 
Combinatorial Optimization Majority colorings of sparse digraphs 
A Majority kcoloring of a directed graph is an assignment of k colors to its vertices in such a way that every vertex has the same color as at most half of its outneighbors. It is known that every digraph is majority 4colorable, but it remains an open question whether every digraph is majority 3colorable. The authors of the paper validate this conjecture for digraphs with a chromatic number at most 6 and digraphs with a dichromatic number at most 3. They also prove analogous theorems for list coloring: digraphs with a list chromatic number at most 6 or list dichromatic number at most 3 are majority 3choosable. The paper also investigates which digraphs are majority 2colorable: the authors show that digraphs without directed odd cycles are majority 2colorable, but in general deciding whether a given digraph is majority 2colorable is NPcomplete. The last result proposed in this paper is proof that every digraph has a fractional majority of 3.9602coloring. 
17.11.2022 16:00 Piotr Kaliciak 
Combinatorial Optimization A counterexample to the lights out problem 
In the basic Lights Out problem, we are given the undirected graph of turnedoff lights, and our goal is to turn on all the lights. In the generalized version of this problem, our mission is to assign every vertex a value from 0 to p, such that for every vertex, the sum of values in its neighbors is equal to 0 mod p. The authors not only prove that a generalized version of this problem isn't always solvable but also they show conditions, under which the problem has a solution. 
17.11.2022 14:15 Bartłomiej Błoniarz, Hubert Dej 
Algorytmika More on ChangeMaking 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 (changemaking) 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 alltargets), 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: 
16.11.2022 16:15 Hoang La Jagiellonian 
Theoretical computer science 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 3connected cubic graphs. They unite Tait's, Barnette's, and Tutte's conjectures on Hamiltonicity in cubic graphs, NeumannLara'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 3connected, 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 vertexpartitioned 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 
Computer science foundations 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 selfdual, 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 
Combinatorial Optimization 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. 
10.11.2022 16:00 Justyna Jaworska 
Combinatorial Optimization 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. 
09.11.2022 16:15 Wojciech Czerwiński University of Warsaw 
Theoretical computer science Reachability problem in Vector Addition Systems 
Recently we managed with coauthors to settle the complexity of the reachability problem for Vector Addition Systems (VASes) to be Ackermanncomplete. 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 Ackermannhardness for the reachability problem and which hopefully may help in solving the remaining challenges. 
03.11.2022 16:45 Jędrzej Kula 
Combinatorial Optimization 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))). 
03.11.2022 16:00 Krzysztof Ziobro 
Combinatorial Optimization 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. 
03.11.2022 14:15 Katarzyna Kępińska, Sebastian Spyrzewski 
Algorytmika Fully Dynamic FourVertex Subgraph Counting 
02.11.2022 16:15 Jędrzej Hodor Jagiellonian 
Theoretical computer science Dimension of planar posets 
It is a longstanding open problem if posets with a planar cover graph are dimbounded (meaning that large dimension yields a large standard example as a subposet). This notion is the posets' counterpart of the wellstudied χboundedness in the graph theory. In my talk, I will focus on summarizing the new progress in this area. The dimboundedness 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 
Computer science foundations Canceled 
27.10.2022 16:00 Bartłomiej Bosek 
Combinatorial Optimization On a Problem of Steinhaus 
Let N be a positive integer. A sequence X=(x_{1},x_{2},…,x_{N}) of points in the unit interval [0,1) is piercing if {x_{1},x_{2},…,x_{n}}∩[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=(x_{1},x_{2},…,x_{f(N)}) is fpiercing if {x_{1},x_{2},…,x_{f(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(d^{3}) 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 stickbreaking games, we prove here that the function s(d) satisfies ⌊c_{1}d⌋⩽s(d)⩽c_{2}d+o(d), where c_{1}=ln2/(1−ln2)≈2.25 and c_{2}=(1+ln2)/(1−ln2)≈5.52. We also prove that there exists an infinite fpiercing 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. 
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 I_{s}, I_{t} i chcemy stwierdzić czy istnieje sekwencja I_{1}, …, I_{s} zbiorów niezależnych w G taka, że I_{1} = I_{s}, I_{l} = I_{t} oraz I_{i} ∆ I_{i+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 fixedparameter tractable (FPT). 
26.10.2022 16:15 Dömötör Pálvölgyi Eötvös Loránd University 
Theoretical computer science 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 131072^{n} to 3.55^{n}. 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 
Computer science foundations 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^{n1} 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 
Combinatorial Optimization 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 outneighbors. 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. 
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 NPzupeł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(2^{o(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 
Theoretical computer science 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 
Computer science foundations Short Proofs of Normalization for the simplytyped λ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 
Combinatorial Optimization 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 kcolorable at all times, and the updates consist of insertions only, then we can achieve the amortized recourse budget of O(k^{7}logn) 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 circulararc 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 nonintersecting unit arcs of size L^{2}−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 ZychPawlewicz. 
12.10.2022 16:15 Friedrich Eisenbrand École Polytechnique Fédérale de Lausanne 
Theoretical computer science 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 
Computer science foundations Implicit computation complexity in higherorder 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 higherorder 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 
Combinatorial Optimization Dimension of planar posets 
It is a longstanding open problem if planar posets are dimbounded (an analog of chibounded 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 dimboundedness in the case of posets with planar cover graphs and a zero. 
05.10.2022 16:15 Paul Seymour Princeton University 
Theoretical computer science Getting closer to the ErdősHajnal conjecture 
A general nvertex 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ősHajnal conjecture (from 1977) says that for every graph H, there exists c such that every Hfree 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.

15.06.2022 16:15 Piotr Micek Jagiellonian 
Theoretical computer science Boolean dimension and dimboundedness 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(log^{2}n) 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. 
09.06.2022 16:15 Bartłomiej Bosek 
Combinatorial Optimization 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 
Theoretical computer science Local consistency methods in Solving CSPs and CSPlike problems over omegacategorical structures 
FederVardi 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 (FederVardi) conjecture, i.e., CSP(B) for a finite structure B is either in P or it is NPcomplete, 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 firstorder reducts B of finitely bounded homogeneous structures, all of which are in particular omegacategorical. 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 finitedomain 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 CSPlike problems over omegacategorical structures. 
08.06.2022 12:15 Karolina Gontarek 
Computer science foundations 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^{k1}

02.06.2022 17:00 Krzysztof Pióro 
Combinatorial Optimization Brooks' Theorem via the AlonTarsi Theorem 
Brooks' Theorem states that every connected graph G with maximum degree d is dcolorable 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 AlonTarsi Theorem and it remains valid in a more general choosability version of Brooks' theorem. 
02.06.2022 16:15 Demian Banakh 
Combinatorial Optimization 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 wellknown 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. 
02.06.2022 14:15 Jędrzej Kula, Maciej Nemś 
Algorytmika Towards SubQuadratic Diameter Computation in Geometric Intersection Graphs 
Grafy przecięć geometrycznych to grafy, gdzie wierzchołki odpowiadają figurom geometrycznym w dwymiarowej 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 
Computer science foundations EFFICIENT FULL HIGHERORDER UNIFICATION by PETAR VUKMIROVIC, ALEXANDER BENTKAMP, AND VISA NUMMELIN 
We developed a procedure to enumerate complete sets of higherorder 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 higherorder 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 
Combinatorial Optimization Digraphs are 2weight 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 2weightchoosability. 
26.05.2022 16:15 Łukasz Selwa 
Combinatorial Optimization A better lower bound on average degree of 4listcritical graphs 
A graph G is klistcritical if it is not (k1)choosable, but every proper subgraph of G is (k1)choosable. We give a new lower bound for the average degree of incomplete klistcritical graphs and online klistcritical graphs. The presented bound improves the earlier known lower bounds for k = 4,5,6.

 Home
 Algorithmics Research Group
 Foundations of Computer Science
 Faculty of Mathematics and Computer Science
 Contact
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Photos
 People
 Bartłomiej Bosek
 Iwona Cieślik
 Jan Derbisz
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Agnieszka Łupińska
 Marcin Mazur
 Piotr Micek
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Wojciech Szpankowski
 Maciej Ślusarek
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Former colleagues