Seminaria
04.10.2023 16:15 Avi Widgerson Institute for Advanced Study, Princeton 
Informatyka Teoretyczna The Value of Errors in Proofs 
Recently, a group of theoretical computer scientists posted a paper on the Arxiv with the strangelooking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of vonNeumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here https://arxiv.org/abs/2001.043 
11.10.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.10.11 
18.10.2023 16:15 Marcelo Campos University of Oxford 
Informatyka Teoretyczna An exponential improvement for diagonal Ramsey 
The Ramsey number R(k) is the minimum n such that every redblue colouring of the edges of the complete graph K_{n} on n vertices contains a monochromatic copy of K_{k}. We prove that R(k)≤3.99^{k}. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

25.10.2023 16:15 Torsten Mütze University of Warwick 
Informatyka Teoretyczna A book proof of the middle levels theorem 
In this lecture I present an elementary and fully selfcontained proof of the middle levels conjecture (now theorem), which asserts that the subgraph of the (2n+1)dimensional hypercube induced by all bitstrings with Hamming weight n or n+1 admits a Hamilton cycle for every n≥1. 
08.11.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.11.08 
15.11.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.11.15 
22.11.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.11.22 
29.11.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.11.29 
06.12.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.12.06 
13.12.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.12.13 
20.12.2023 16:15 TBA 
Informatyka Teoretyczna TBA  2023.12.20 
03.01.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.01.03 
10.01.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.01.10 
17.01.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.01.17 
24.01.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.01.24 
28.02.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.02.28 
06.03.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.03.06 
13.03.2024 16:15 TBA 
Informatyka Teoretyczna TBA  2024.03.13 
Poprzednie referaty
15.06.2023 16:45 Julia Biały 
Optymalizacja Kombinatoryczna A game generalizing Hall's Theorem 
Authors investigate starting positions in a particular twoplayer game, considering scenarios where the first player can have a winning strategy. This work offers a broader interpretation of Hall's Theorem using Vizing's Theorem on edgecoloring in a specialized setting.

15.06.2023 16:00 Łukasz Selwa 
Optymalizacja Kombinatoryczna Orientations of Graphs with Prescribed Weighted OutDegrees 
We study the complexity of the orientation problem where the outneighborhood of every vertex is bounded by some function. This problem can be used to apply Galvin’s kernel method to show that graph G satisfies a certain coloring property. We show that the problem is NPcomplete in the case of graphs that are bipartite, planar, and of maximum degree at most 3. We also prove some results on the (f,g)choosability problem for weighted graphs, including a generalization of Brooks's theorem for weighted graphs. 
14.06.2023 16:15 Fabrizio Frati Università Roma Tre 
Informatyka Teoretyczna Currents Trends and Hot Problems in Graph Drawing 
In this expository talk, I will discuss the topics that have attracted the most attention in the graph drawing community in recent years. The talk will try to convey the direction where the research in graph drawing is going, with a focus on the most intriguing open problems in the field. 
07.06.2023 16:15 Michał Seweryn Université Libre de Bruxelles 
Informatyka Teoretyczna Recent results in graph product structure theory 
Graph product structure theory describes complicated graphs as subgraphs of strong products of simpler building blocks. Usually, the strong product involves three graphs: a graph of bounded treewidth, a small complete graph, and a path. For example, Dujmović et al. showed that every planar graph is a subgraph of the strong product of a treewidth3 graph, a complete graph on three vertices, and a path. This theorem has been the key to solving many longstanding problems about planar graphs, and is arguably the most important result of the graph product structure theory. In my talk I will discuss some of the recent results in this field. First I will discuss two generalizations of the product structure theorem for planar graphs to kplanar graphs and kpowers of planar graphs with bounded degree. The distinguishing property of these theorems is that the bound on the treewidth in the product is an absolute constant independent of k and the maximum degree. Then, I will discuss some product structure theorems, where an nvertex graph is a subgraph of the strong product of two graphs: a graph of constant treewidth, and a complete graph on O(√n) vertices. These theorems are qualitative strengthenings of √nseparator theorems by LiptonTarjan and AlonSeymourThomas. Joint works with Marc Distel, Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David Wood 
31.05.2023 16:15 Ola Svensson École Polytechnique Fédérale de Lausanne 
Informatyka Teoretyczna The Price of Explainability for Clustering 
Given a set of points in ddimensional space, an explainable clustering is one where the clusters are specified by a tree of axisaligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worstcase ratio between the cost of the best explainable clusterings to that of the best clusterings.
We show that the price of explainability for kmedians is at most 1+H_{k−1}; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least (1−o(1))·ln k, showing that our result is best possible, up to lowerorder terms. We also improve the price of explainability for the kmeans problem to O(k·lnln k) from the previous O(k·ln k), considerably closing the gap to the lower bounds of Ω(k).
Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable kmedians and kmeans cannot be approximated better than O(ln k), under standard complexitytheoretic conjectures. This essentially settles the approximability of explainable kmedians and leaves open the intriguing possibility to get significantly better approximation algorithms for kmeans than its price of explainability.
This is joint work with Anupam Gupta, Madhusudhan Reddy Pittu, and Rachel Yuan 
25.05.2023 16:45 Katarzyna Król 
Optymalizacja Kombinatoryczna Ball Packings and Lorentzian Discrete Geometry 
The problem of packing balls is to find an arrangement of spheres in space so that no spheres overlap. It is popular in the literature to consider packing disks  i.e. twodimensional spheres. A tangency graph is a graph whose vertices are balls and whose edge is between vertices u and v if ball u and ball v touch each other. We study ball packings whose tangency graph is a higher dimensional grid graph. We give a loose bound on the size of such grid graphs that admit a ball packing.

25.05.2023 16:00 Jędrzej Kula 
Optymalizacja Kombinatoryczna Playing cards with Vizing's demon 
The paper's authors present a parametrized version of the solitaire game. In this version, players play against a demon whose task is to rearrange cards after each move in a way that the player will not be able to win the game. By defining a specific demon strategy and finding the winning strategy against it, one may prove König and Vizing theorems.

24.05.2023 16:15 Csaba Tóth California State University, Northridge 
Informatyka Teoretyczna Optimal spanners in Euclidean spaces 
For a set S of n points in a metric space (X,d) and a parameter t>1, a tspanner is a weighted graph G=(S,E) such that the shortest path distance in G approximates the pairwise distances in the metric space up to a factor of at most t (stretch factor). This talk focuses on the ddimensional Euclidean space in the regime where t is close to 1. Recent research uncovered tight tradeoffs for two important quality measures for tspanners: the sparsity E(G)/n and the lightness w(G)/w(MST(S)). We present an algorithm that constructs a tspanner for a given set of n points in Euclidean dspace, by sparsifying classical Yaographs, that attains a worstcase optimal bound on the weight of the spanner. In the online model, a sequence of points arrive onebyone, and we need to maintain a tspanner for the first n points for all n. By combining sparse Yaographs and hierarchical clustering, we obtain an online algorithm that maintains a light spanner and achieves logarithmic competitive ratio compared to the offline optimum. 
18.05.2023 16:45 Krzysztof Barański 
Optymalizacja Kombinatoryczna A note on degreeconstrained subgraphs 
Last semester I presented a paper “A note on polynomials and ffactors of graphs” by Hamed Shirazi and Jacques Verstraëte, who proved two ffactor theorems using the Combinatorial Nullstellensatz. In this work, authors take a closer look at the same theorems and prove them in a different way.

18.05.2023 16:00 Filip Konieczny 
Optymalizacja Kombinatoryczna On constructive methods in the theory of colourcritical graphs 
kcritical graph is not (k1)colorable but every proper subgraph is. The authors take a constructive approach to the theory of critical graphs and show methods of how such graphs can be constructed, composed, and augmented, additionally discussing the advantages and drawbacks of these methods. 
17.05.2023 16:15 John Iacono Université Libre de Bruxelles 
Informatyka Teoretyczna The pursuit of the dynamic optimality conjecture via the geometry of binary search trees 
In 1983, Sleator and Tarjan introduced the splay tree, a selfadjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotationbased search tree algorithm on every sufficiently long sequence — any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. In doing so we will present the geometric view of binary search trees, introduced in 2009, where we (with Erik D. Demaine, Dion Harmon, Daniel M. Kane and Mihai Pătraşcu) showed an equivalence between binary search tree algorithms and a simple combinatorial property of points in the plane. Almost all recent progress, which we will survey, towards the fortyyearold dynamic optimality conjecture since then has used this view, as it greatly simplifies reasoning about binary search trees. 
11.05.2023 16:45 Rafał Pyzik 
Optymalizacja Kombinatoryczna Improved lower bounds on the number of edges in list critical and online list critical graphs 
A graph G is kcritical if it is not (k1)colorable, but every proper subgraph of G is. Authors improve the bound by Kostochka and Stiebitz for a number of edges in kcritical graphs. The same bound holds for klistcritical and online klistcritical graphs improving the bound established by Riasat and Schauz. This result follows from analyzing AlonTarsi orientable induced subgraphs satisfying certain conditions. 
11.05.2023 16:00 Aleksander Katan 
Optymalizacja Kombinatoryczna A not 3choosable planar graph without 3cycles 
An Llist coloring of graph G is a proper vertex coloring in which every vertex receives a color from a prescribed list L(v). G is said to be kchoosable, if all lists L(v) have cardinality k, and G is Lcolorable for any assignment of those lists. The author presents a planar graph without 3cycles that is not 3choosable. We will also discuss other topics related to list colorings, such as the fact that every planar graph is 5choosable. 
10.05.2023 16:15 Clément Rambaud École Normale Supérieure, PSL Paris 
Informatyka Teoretyczna Neighborhood complexity of planar graphs 
In a class of graphs of bounded expansion, for every graph in the class, for every nonempty set A of vertices, for every radius r, the number of distinct intersections between A and a ball of radius r is at most f(r)·A for some function f depending only on the considered class [Reidl, Sánchez Villaamil and Stravopoulos, 2019]. The function f coming from existing proofs is typically exponential. We prove that in the special case of planar graphs, f can be taken to be a polynomial, and more precisely in O(r^{4}). We also show that a polynomial bound holds more generally for every proper minorclosed class of graphs. This is joint work with Gwenaël Joret. 
04.05.2023 16:45 Rafał Kilar 
Optymalizacja Kombinatoryczna On the structure of kconnected graphs without K_kminor 
The famous Hadwiger's Conjecture states that every kchromatic graph must contain the clique K_{k} as a minor. It remains unproven for k>6. Motivated by this conjecture we can ask about the structure of kconnected graphs without K_{k} as a minor. We show that any such graph can't have three (k2)cliques that share at most three vertices, which is a generalization of previous results in the area. 
04.05.2023 16:00 Bartłomiej Błoniarz 
Optymalizacja Kombinatoryczna Pólya's Permanent Problem 
The permanent of a square matrix is a function very similar to the determinant. It has important applications in counting problems, but computing it is a #Pcomplete problem. In 1913, Pólya proposed a method to calculate permanents using determinants, which was soon proven to be faulty in certain cases. This led to the question of when Pólya's method can be used, known as Pólya's Permanent Problem. The article provides an overview of the problem, including equivalent versions and a solution to one of the formulations.

27.04.2023 16:45 Demian Banakh 
Optymalizacja Kombinatoryczna Flip distance to a noncrossing perfect matching 
A noncrossing perfect matching is Euclidean matching on 2n points so that no 2 segments cross. Given some crossing matching, we can iteratively apply the flip operation (fix any 2 crossing segments, and swap the endpoints so that they don't cross) to eventually arrive at a noncrossing matching. We will investigate the upper and lower bounds for the number of flips sufficient and necessary to eliminate all crossings. It is conjectured that θ(n^{2}) flips are always sufficient. 
27.04.2023 16:00 Szymon Salabura 
Optymalizacja Kombinatoryczna Edge lower bounds for list critical graphs, via discharging 
We say that a graph G is kchoosable if G has a proper coloring from every list assignment L with L(v)=k for every vertex v. A graph G is klistcritical if it's not kchoosable, but every proper subgraph of G is. The problem of bounding the number of edges from below in such graphs has been widely studied, starting with the work of Gallai. The authors present a rephrased version of his proof using the discharging method and improve the original result by presenting additional properties of such graphs, enabling a different set of discharging rules.

27.04.2023 14:15 Justyna Jaworska, Jakub Siuta 
Algorytmika Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance 
Dla problemów znjadowania odległości edycyjnej i odległości edycyjnej Dycka chcemy znaleść szybkie, deterministyczne i proste aproksymacje, z być może dużym współczynnikiem aproksymacji. Dla klasycznej odległości edycyjnej wprowadzimy klasę szybkich i prostych algorytmów nazywanych "algorytmami pojdedycznego skanowania". Saha, w 2014. roku, podał randomizowany algorytm z tej klasy osiągający aproksymację O(d) dla słow x, y takich że ich ogległość edycyjna jest rzędu O(d). W tej pracy prezentujemy: (1) deterministyczny algorytm z wymienionej klasy osiągający podobne rezultaty oraz (2) dowodzimy, że nie istnieje (nawet randomizowany) algorytm z tej klasy, który dawałby lepszą aproksymację. Dla odległości edycyjnej Dycka, Saha zaproponował randomizowaną redukcję z odległości edycyjnej Dycka do klasycznej odległości edycyjnej o koszcie O(log d), gdzie d to odległość edycyjna Dycka. Podamy redukcję deterministyczną której zarówno sfromułowanie jak i udowodnienie poprawności jest prostsze. 
26.04.2023 16:15 David Eppstein University of California, Irvine 
Informatyka Teoretyczna The Complexity of Iterated Reversible Computation 
Reversible computation has been studied for over 60 years as a way to evade fundamental physical limits on the power needed for irreversible computational steps, and because quantum computing circuits are necessarily reversible. We study a class of problems based on computing the iterated values of a reversible function. The story leads through Thomason's lollipop algorithm in graph theory, circuit complexity, and reversible cellular automata, to card shuffling, the reflections of light in jewels, and curves on topological surfaces, and involves both PSPACEhard problems and problems with unexpected polynomialtime algorithms. 
20.04.2023 16:45 Piotr Kaliciak 
Optymalizacja Kombinatoryczna Decomposing 4connected planar triangulations into two trees and one path 
A graph is 4connected if no matter which 4 vertices we remove from it, it remains connected. We can decompose every 4connected planar triangulation into a Hamiltonian path and two trees. Moreover, we can decompose any Hamiltonian planar triangulation into two trees and one spanning tree of degree at most 3. These results are bestpossible, this means that we cannot decrease the maximum degree of the first tree. 
20.04.2023 16:00 Kamil Galewski 
Optymalizacja Kombinatoryczna On the discrepancy of circular sequences of reals 
The discrepancy is a function that measures the irregularity of the distribution of a given sequence of real numbers. The authors present a new method to measure discrepancy for sequences of reals lying on a circle of circumference 1, as a more sensitive alternative to the previously known functions. They also show a tight upper bound for this function.

19.04.2023 16:15 Pat Morin Carleton University 
Informatyka Teoretyczna Proof of the Clustered Hadwiger Conjecture 
Hadwiger's Conjecture asserts that every K_{h}minorfree graph is properly (h1)colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_{h}minorfree graph is (h1)colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed t≥s, we show that every K_{s,t}minorfree graph is (s+1)colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. This joint work with Vida Dujmović, Louis Esperet, and David R. Wood. 
13.04.2023 16:45 Łukasz Gniecki 
Optymalizacja Kombinatoryczna Sequences of points on a circle 
Consider a sequence of points a_{1}, a_{2}, a_{3}, ... on a circle with radius 1/(2π), in other words, numbers mod 1. The numbers a_{1}, a_{2}, ..., a_{n} define n intervals with a total length of 1. Denote by M[n,r](a) and m[n,r](a) the largest and the smallest length of consecutive r intervals. We can think of how the values n·M[n, r](a) and n·m[n, r](a) will behave if we go with n to infinity. In particular, for a given sequence a we can find the upper limit of n·M: L[r](a) = limsup n·M[n,r](a) and the lower limit of n·m: l[r](a) = liminf n·m[n,r](a). We can go further and consider the greatest lower bound on L[r](a) (g.l.b. in short) and the lowest upper bound on l[r](a) (l.u.b. in short), overall sequences a. The authors derive bounds on this g.l.b. and l.u.b. and in the case of r = 1, they prove these bounds are tight by giving an example of a sequence a which satisfies these bounds. 
13.04.2023 16:00 Ignacy Buczek 
Optymalizacja Kombinatoryczna 10 Problems for Partitions of Trianglefree Graphs 
The original sparse halves conjecture of Erdos, formed in 1976, states that every trianglefree graph has a subset of n/2 vertices with at most n^{2}/50 edges. As it still remains unsolved, a number of related problems have been stated in order to better understand the problems of partitioning graphs into sparse subsets. In our work, we present and improve the results of some of the existing problems of this kind, and in addition, we state multiple new ones and provide initial results. 
13.04.2023 14:15 Rafał Pyzik, Sebastian Spyrzewski 
Algorytmika Treewidth is NPComplete on Cubic Graphs (and related results) 
Autorzy pracy podają prosty dowód NPzupełności problemu Treewidth, udowadniając jego NPzupełność w klasie dopełnień grafów dwudzielnych. Praca poprawia też rezultat Bodlaedera i Thilikosa z roku 1997 mówiący, że Treewidth jest NPzupełne w grafach o maksymalnym stopniu co najwyżej 9, pokazując NPzupełność w grafach regularnych stopniu 3. 
12.04.2023 16:15 Ruta Mehta University of Illinois at UrbanaChampaign 
Informatyka Teoretyczna Competitive division of goods, bads, and mixed: existence, computation, and complexity 
Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This ageold problem, mentioned even in the Bible, arises naturally in a wide range of reallife settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are nondisposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed). I will first consider the case of additive valuations, where when all items are goods, the CE set is wellknown to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this nonconvexity through a new exteriorpoint method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinatewise monotone function over linear constraints. Finally, I will discuss recent developments on the exchange setting (barter system) on existence and computational complexity. Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin. 
05.04.2023 16:15 Ralph Keusch Siemens Mobility CH 
Informatyka Teoretyczna A Solution to the 123 Conjecture 
In 2004, Karoński, Łuczak and Thomason conjectured that for each connected graph on at least 3 vertices, it is possible to assign weights from {1,2,3} to the edges such that neighboring vertices always obtain different weighted degrees. Recently, Przybyło verified the conjecture for all graphs G where the minimum degree is sufficiently large, compared to the maximum degree and to an absolute constant. In general, the bestknown bound was by Kalkowski, Karoński, and Pfender from 2011. They proved that such an assignment is always possible with the weight set {1,2,3,4,5}. We present a flowbased strategy to construct vertexcoloring edgeweightings and show how it was first used to shrink the general bound to the set {1,2,3,4} and now led to the confirmation of the conjecture. 
30.03.2023 16:45 Jakub Siuta 
Optymalizacja Kombinatoryczna Listavoiding orientations 
Given a graph G with a set F(v) of forbidden values at each v∈V(G), an Favoiding orientation of G is an orientation in which deg_{+}(v)∉F(v) for each vertex v. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if F(v)<12deg(v) for each v∈V(G), then G has an Favoiding orientation, and they showed that this statement is true when 12 is replaced by 14. In this paper, we take a step toward this conjecture by proving that if F(v)<⌊13deg(v)⌋ for each vertex v, then G has an Favoiding orientation. Furthermore, we show that if the maximum degree of G is subexponential in terms of the minimum degree, then this coefficient of 13 can be increased to 2^{1/2}−1−o(1) ≈ 0.414. Our main tool is a new sufficient condition for the existence of an Favoiding orientation based on the Combinatorial Nullstellensatz of Alon and Tarsi.

30.03.2023 16:00 Grzegorz Gawryał 
Optymalizacja Kombinatoryczna Critically paintable, choosable or colorable graphs 
The concept of criticality in graphs was introduced around 1950 to capture the essence of a graph that is not colorable with k colors. Since then, the idea became more and more popular in the literature. We will generalize the results about criticality to list and online list coloring of graphs, using a stronger version of Brooks and Gallai's theorems and prove their implications for graphs drawn on different surfaces, basically showing, that for any surface and k ≥ 5, there are always only finitely many critical graphs for both paintability and choosability.

30.03.2023 14:15 Łukasz Grobelczyk, Rafał Loska 
Algorytmika This Game is Not Going to Analyze Itself 
Praca analizuje kilka problemów powiązanych z grą przeglądarkową "This Game Is Not Going To Load Itself", w której gracz ma za zadanie przekierować poruszające się kolorowe kwadraty do odpowiedniego ujścia na planszy poprzez ustawianie na niej kolorowych strzałek. Problem decyzyjny czy można wygrać grę jest w klasie $\Sigma_2^P$, jest NPtrudny w wersji offline, a nawet bez możliwości układania strzałek przez gracza jest zarówno NP jak i coNPtrudny. Praca analizuje również problem istnienia strategii wygrywającej. 
29.03.2023 16:15 Alex Scott University of Oxford 
Informatyka Teoretyczna On a problem of ElZahar and Erdős 
Two subgraphs A,B of a graph G are anticomplete if they are vertexdisjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by ElZahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number. Second, we look at what happens if we replace the hypothesis that G has large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K_{t}, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding a complete graph we exclude a complete bipartite graph. Finally, we discuss analogous problems for tournaments. This is joint work with Tung Nguyen and Paul Seymour. 
23.03.2023 16:45 Tomasz Mazur 
Optymalizacja Kombinatoryczna A note on large induced subgraphs with prescribed residues in bipartite graphs 
A known result of Scott is that for every k ≥ 2, there exists a constant c(k) > 0 such that every bipartite nvertex graph G without isolated vertices has an induced subgraph H on at least c(k)·n vertices such that deg_{H}(v) = 1 (mod k) for every vertex v in H. Scott conjectured that c(k) = Ω(1/k). A confirmation of this conjecture is supplied in this paper.

23.03.2023 16:00 Katzper Michno 
Optymalizacja Kombinatoryczna Dimension and cut vertices: an application of Ramsey theory 
Dimension of a poset P (denoted dim(P)), is the smallest natural number d, such that there are d linear extensions of P s.t. their intersection is exactly P. Among many results regarding the poset dimension, there are quite a few that find relationships between the dimension and some properties of its cover graph. We will discuss one such result, that if for every block B in the cover graph of P, the induced subposet of P with ground set B has dimension at most d, then dim(P) ≤ d+2. We will also show constructions of examples proving that this bound is tight using Product Ramsey Theorem. 
22.03.2023 16:15 Martin Grohe RWTH Aachen 
Informatyka Teoretyczna A Deep Dive into the WeisfeilerLeman Algorithm 
The WeisfeilerLeman algorithm is a wellknown combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semidefinite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the WeisfeilerLeman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications. 
16.03.2023 16:00 Jakub Dziarkowski 
Optymalizacja Kombinatoryczna Research problems 
We will discuss selected open problems in discrete mathematics. Two of them are connected to discrete geometry: Piercing families of planar convex sets  finding the minimum number of points needed to pierce a collection of convex sets in the plane, Splitting lines for planar point sets  splitting set of points equally by line through points of this set. Other are graph theory problems: Acyclic edgecoloring of graphs, Two questions on long cycles, and Representations of graphs modulo n.

15.03.2023 16:15 Sebastian Siebertz Universität Bremen 
Informatyka Teoretyczna Advances in algorithmic metatheorems 
Algorithmic metatheorems provide general explanations when and why certain algorithmic problems can be solved efficiently. They are typically formulated in terms of logic (defining the descriptive complexity of the problems) and structural properties of their inputs. A prototypical algorithmic metatheorem is Courcelle’s Theorem, stating that every graph property definable in monadic secondorder logic (MSO) can be decided in linear time on every graph class of bounded treewidth. Similarly, every graph property definable in firstorder logic (FO) can be tested efficiently on every nowhere dense graph class. In this talk I will present recent progress on algorithmic metatheorems for FO on dense graph classes as well as for logics whose expressive power lies between MSO and FO. The presented results reveal beautiful connections between structural graph theory, classical model theory and algorithmics. 
09.03.2023 16:00 Jędrzej Hodor 
Optymalizacja Kombinatoryczna Obstacle Number of Graphs 
An obstacle is a connected shape on the plane. Given a set of obstacles and a set of points on the plane, we can define a visibility graph on the set of points. Two points are connected by an edge if a straight line between them is disjoint from all the obstacles. We say that the set of points and obstacles is an obstacle representation of the resulting graph. We define the obstacle number of a graph as the minimum number of obstacles needed to represent the graph in an obstacle representation. This parameter was introduced by Alpert, Koch, and Laison in 2011. I will discuss many examples of graphs and their obstacle numbers. I will also present a related notion of convex obstacle number. Moreover, during the presentation, I will state many interesting open problems. 
08.03.2023 16:15 Sándor KisfaludiBak Aalto University 
Informatyka Teoretyczna On geometric variants of TSP and Steiner tree 
In the classic Euclidean traveling salesman problem, we are given n points in the Euclidean plane, and the goal is to find the shortest round trip that visits all the points. We will discuss some of the key techniques that allowed us to find (conditionally) optimal exact and approximation algorithms for this problem, while the closely related Steiner tree problem seems to resist many similar attempts. We will then turn to the traveling salesman or Steiner tree with "neighborhoods". Here instead of points, we are given a set of affine subspaces, and the goal is to find the shortest round trip or tree that intersects each subspace. It turns out that these problems have a different computational complexity than the classic problems with points: they require a completely novel approach for the hyperplane case, while the other cases remain largely unresolved. 
01.03.2023 16:15 Mikkel Thorup University of Copenhagen 
Informatyka Teoretyczna Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) 
We consider the numerical taxonomy problem of fitting an SxS distance matrix D with a tree metric T. Here T is a weighted tree spanning S where the path lengths in T induce a metric on S. If there is a tree metric matching D exactly, then it is easily found. If there is no exact match, then for some k, we want to minimize the L_{k} norm of the errors, that is, pick T so as to minimize DT_{k} = (Σ_{i,jϵS} D(i,j)T(i,j)^{k}) ^{1/k}. An evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NPhard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC). The numerical taxonomy problem is important in practice and many heuristics have been proposed. In this talk we will review the basic algorithmic theory, results and techniques, for the problem, including the most recent result from FOCS'21 [Vincent CohenAddad et al., 2021]. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining.  At STOC'93, Farach, Kannan, and Warnow [Martin Farach et al., 1995] proved that under L_{∞}, we can find the optimal ultrametric. Almost all other variants of the problem are APXhard  At SODA'96, Agarwala, Bafna, Farach, Paterson, and Thorup [Richa Agarwala et al., 1999] showed that for any norm L_{k}, k≥1, if the best ultrametric can be αapproximated, then the best tree metric can be 3αapproximated. In particular, this implied a 3approximation for tree metrics under L_{∞.}  At FOCS'05, Ailon and Charikar [Nir Ailon and Moses Charikar, 2011] showed that for any L_{k}, k≥1, we can get an approximation factor of O(((log n)(log log n))^{1/k}) for both tree and ultrametrics. Their paper was focused on the L_{1} norm, and they wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".  At FOCS'21, CohenAddad, Das, Kipouridis, Parotsidis, and Thorup [Vincent CohenAddad et al., 2021] showed that indeed a constant factor is possible for L_{1} for both tree and ultrametrics. This uses the special structure of L_{1} in relation to hierarchies.  The status of L_{k }is wide open for 1<k<∞. All we know is that the approximation factor is between Ω(1) and O((log n)(log log n)). 
26.01.2023 16:45 Krzysztof Barański 
Optymalizacja Kombinatoryczna A note on polynomials and ffactors of graphs 
A kfactor of a graph is a spanning kregular subgraph. Here, we will focus on a more general term: ffactors of graphs, where f is a function assigning to each vertex of the graph a set of integers from 0 to the degree of that vertex, and ffactor is a spanning subgraph of the graph, where for every vertex v, degree of v is an element of f(v). Authors show a necessary condition for such ffactors.

26.01.2023 16:00 Demian Banakh 
Optymalizacja Kombinatoryczna 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 
Informatyka Teoretyczna 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 
Podstawy Informatyki 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 
Optymalizacja Kombinatoryczna A Survey of the Game “Lights Out!" 
In the most common version of the Lights Out problem, we have an undirected graph G, in which every vertex represents a light either on or off. We can toggle any light, but such action is always followed by all the neighboring lights also switching. The goal is to decide whether it is possible to turn all the lights off. The authors collected many results regarding this problem to present them in a unified framework. For example, they show proof that for any graph with all the lights initially on, it is possible to turn them off. They also study the optimization variants of the problem, such as finding the minimum number of lights we need to toggle, which they show to be NPhard.

19.01.2023 16:00 Jakub Dziarkowski 
Optymalizacja Kombinatoryczna Note on Perfect Forests 
A spanning forest F of a graph G is called a perfect forest if all its components are induced subgraphs of G and the degree of each vertex x in F is odd. It is easy to see that if a connected graph G has a perfect forest, then G is of even order. Interestingly, the opposite implication is also true (A.D. Scott was the first to prove it). Gregory Gutin gave a short proof of this theorem using linear algebra.

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 
Informatyka Teoretyczna 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 
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 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 
Optymalizacja Kombinatoryczna 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 
Optymalizacja Kombinatoryczna 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 
Informatyka Teoretyczna 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 
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 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 
Optymalizacja Kombinatoryczna 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 
Optymalizacja Kombinatoryczna 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 
Informatyka Teoretyczna 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 
Podstawy Informatyki 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 
Optymalizacja Kombinatoryczna 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 
Optymalizacja Kombinatoryczna 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 
 Strona Główna
 Katedra Algorytmiki
 Katedra Podstaw Informatyki
 Wydział Matematyki i Informatyki
 Kontakt
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Galeria
 Ludzie
 Bartłomiej Bosek
 Marcin Briański
 Iwona Cieślik
 Jan Derbisz
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Xuân La
 Agnieszka Łupińska
 Piotr Micek
 Jonathan Narboni
 Andrzej Pezarski
 Bartosz Podkanowicz
 Adam Polak
 Krzysztof Potępa
 Wojciech Szpankowski
 Maciej Ślusarek
 Jan Tułowiecki
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Byli współpracownicy