Seminaria
20.11.2018 16:15 Dawid Tracz 
Algorytmy Randomizowane i Aproksymacyjne Finding Cliques in Social Networks: A New DistributionFree Model (Fox, Roughgarden, Seshadhri, Wei, Wein) 
21.11.2018 12:14 Marcin Briański 
Podstawy Informatyki On the compressibility of finite languages and formal proofs by Sebastian Eberhard and Stefan Hetzl 
We consider the minimal number of productions needed for a grammar to cover a finite language L as the grammatical complexity of L. We study this measure for several types of word and tree grammars and show that it is closely connected to wellknown measures for the complexity of formal proofs in firstorder predicate logic. We construct an incompressible sequence of finite word languages and transfer this and several other results about the complexity of word and tree languages to formal proofs 
22.11.2018 14:00 Rafał Byczek, Bruno Pitrus 
Algorytmika Approximating Edit Distance Within Constant Factor in Truly SubQuadratic Time 
Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów. Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym. W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)). 
27.11.2018 16:15 Dominika Salawa 
Algorytmy Randomizowane i Aproksymacyjne Induced trees in graphs of large chromatic number (Scott) 
28.11.2018 12:14 Jacek Kurek i Bruno Pitrus 
Podstawy Informatyki COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PA 
The subject of enumerative combinatorics is both classical and modern. It is classical, as the basic counting questions go back millennia; yet it is modern in the use of a large variety of the latest ideas and technical tools from across many areas of mathematics. The remarkable successes from the last few decades have been widely publicized; yet they come at a price, as one wonders if there is anything left to explore. In fact, are there enumerative problems that cannot be resolved with existing technology? In this paper we present many challenges in the field from the computational complexity point of view, and describe how recent results fit into the story. 
28.11.2018 16:15 Piotr Kawałek 
Informatyka Teoretyczna TBA 
05.12.2018 12:14 Bartłomiej Puget 
Podstawy Informatyki THE SAFE LAMBDA CALCULUS by WILLIAM BLUM AND LUKE ONG 
Safety is a syntactic condition of higherorder grammars that constrains occurrences of variables in the production rules according to their typetheoretic order. In this paper, we introduce the safe lambda calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simplytyped lambda calculus. In contrast to the original definition of safety, our calculus does not constrain types (to be homogeneous). We show that in the safe lambda calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen. We also propose an adequate notion of betareduction that preserves safety. In the same vein as Schwichtenberg’s 1976 characterization of the simplytyped lambda calculus, we show that the numeric functions representable in the safe lambda calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a characterization of representable word functions. We then study the complexity of deciding betaeta equality of two safe simplytyped terms and show that this problem is PSPACEhard. Finally we give a gamesemantic analysis of safety: We show that safe terms are denoted by Pincrementally justified strategies. Consequently pointers in the game semantics of safe lambda terms are only necessary from order 4 onwards. 
06.12.2018 16:15 Jakub Nowak 
Optymalizacja Kombinatoryczna Box Representations of Embedded Graphs. 
Louis Esperet. Box Representations of Embedded Graphs. Discrete and Computational Geometry, 57 (3): 590606, 2017. ISSN 14320444. doi: 10.1007/s0045401698378. 
12.12.2018 12:14 Dominik Gryboś 
Podstawy Informatyki Characterizing Polynomial and Exponential Complexity Classes in Elementary LambdaCalculus by Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca 
In this paper an implicit characterization of the complexity classes kEXP and kFEXP, for k \geq 0, is given, by a type assignment system for a stratified lambda  calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes kEXP is characterized by a hierarchy of types. 
19.12.2018 12:14 Jakub Łabaj i Gabriela Czarska 
Podstawy Informatyki Programming Languages Capturing Complexity Classes by LARS KRISTIANSEN and PAUL J. VODA 
We investigate an imperative and a functional programming language. The computational power of fragments of these languages induce two hierarchies of complexity classes. Our first main theorem says that these hierarchies match, level by level, a complexitytheoretic alternating spacetime hierarchy known from the literature. Our second main theorems says that a slightly different complexitytheoretic hierarchy (the GoerdtSeidl hierarchy) also can be captured by hierarchies induced by fragments of the programming languages. Well known complexity classes like LOGSPACE, LINSPACE, P, PSPACE etc., occur in the hierarchies. 
19.12.2018 16:15 Grzegorz Gutowski 
Informatyka Teoretyczna TBA 
09.01.2019 12:14 Krzysztof Turowski Purdue University, USA 
Podstawy Informatyki TBA 
16.01.2019 12:14 Rafał Byczek i Paweł Mader 
Podstawy Informatyki A theory of linear typings as flows on 3valent graphs by Noam Zeilberger 
Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or “maps”), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classical notion of an abelian groupvalued “flow” on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3valent graph with boundary) valued in a more general algebraic structure consisting of a preordered set equipped with an “implication” operation and unit satisfying composition, identity, and unit laws. Interesting questions and results from the theory of flows (such as the existence of nowherezero flows) may then be reexamined from the standpoint of lambda calculus and logic. For example, we give a characterization of when the local flow relations (across vertices) may be categorically lifted to a global flow relation (across the boundary), proving that this holds just in case the underlying map has the orientation of a lambda term. We also develop a basic theory of rewriting of flows that suggests topological meanings for classical completeness results in combinatory logic, and introduce a polarized notion of flow, which draws connections to the theory of proofnets in linear logic and to bidirectional typing. 
23.01.2019 12:14 
Podstawy Informatyki COMPLEXITY HIERARCHIES AND HIGHERORDER CONSFREE TERM REWRITING by CYNTHIA KOP AND JAKOB GRUE SIMONSEN 
Constructor rewriting systems are said to be consfree if, roughly, constructor terms in the righthand sides of rules are subterms of the lefthand sides; the computational intuition is that rules cannot build new data structures. In programming language research, consfree languages have been used to characterize hierarchies of computational complexity classes; in term rewriting, consfree firstorder TRSs have been used to characterize P. We investigate consfree higherorder term rewriting systems, the complexity classes they characterize, and how these depend on the type order of the systems. We prove that, for every K ≥ 1, leftlinear consfree systems with type order K characterize $E^K KTIME$ if unrestricted evaluation is used (i.e., the system does not have a fixed reduction strategy). The main difference with prior work in implicit complexity is that (i) our results hold for nonorthogonal TRSs with no assumptions on reduction strategy, (ii) we consequently obtain much larger classes for each type order ($E^K KTIME$ versus $EXP^{K−1}TIME$), and (iii) results for consfree term rewriting systems have previously only been obtained Our work confirms prior results that having full nondeterminism (via overlapping rules) does not directly allow for characterization of nondeterministic complexity classes like NE. We also show that nondeterminism makes the classes characterized highly sensitive to minor syntactic changes like admitting product types or nonleftlinear rules. 
Poprzednie referaty
15.11.2018 16:00 Jakub Łabaj 
Optymalizacja Kombinatoryczna Contracting a Planar Graph Efficiently 
15.11.2018 14:00 Tomasz Zieliński, Michał Zwonek 
Algorytmika On the Complexity of the (Approximate) Nearest Colored Node Problem 
Mając dany graf G = (V, E) gdzie każdy wierzchołek ma przypisany kolor, pytamy o przybliżoną odległość pomiędzy danym wierzchołkiem v a najbliższym jemu kolorowi c. Prezentujemy wyrocznię o rozciągłości 4k5 wykorzystującą O(kn sigma^(1/k)) przestrzeni i O(log k) czasu zapytania. Następnie dowodzimy, że posiadając estymatę rzędu O(polylog(n)) jesteśmy w stanie w czasie O(1) udzielić odpowiedzi na pytanie o dokładną odległość dist(v, c). Na końcu pokazujemy związek pomiędzy problemem lambdaOuMv a odległością dist(v, c). 
14.11.2018 16:15 21.11.2018 16:15 Michał Seweryn 
Informatyka Teoretyczna Bumping a ladder 
We show that every 3connected graph which contains many disjoint 2xngrid minors, contains a 2x(n+1)gridminor. We use this result in a qualitative structure theorem for graphs without large 2xn grids. This is a result from a joint paper with Tony Huynh, Gwenaël Joret, Piotr Micek and Paul Wollan 
14.11.2018 12:14 Mateusz Tokarz 
Podstawy Informatyki Enumerating Proofs of Positive Formulae by GILLES DOWEK AND YING JIANG 
We provide a semigrammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proofterm of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F. 
13.11.2018 16:15 Mateusz Pabian 
Algorytmy Randomizowane i Aproksymacyjne New approximation algorithm for (1,2)TSP (Adamaszek, Mnich, Paluch) 
08.11.2018 16:15 Marcin Muszalski 
Optymalizacja Kombinatoryczna On the queuenumber of graphs with bounded treewidth 
In this talk I will present upper bound for a queuenumber of graphs with bounded treewidth obtained by Veit Wiechert. The new upper bound, 2k  1, improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. Additionally I will show his construction of ktrees that have queuenumber at least k + 1. The construction solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queuenumber of 2trees is equal to 3. Marcin Muszalski. Queuenumber of graphs with bounded treewidth  Veit Wiechert. slides. 2018. 
08.11.2018 14:00 Weronika Grzybowska, Paweł Mader 
Algorytmika Hamming distance completeness and sparse matrix multiplication 
Autorzy prezentują polilogarytmiczne redukcje pomiędzy obliczaniem odległości Hamminga a iloczynem skalarnym, w którym miejsce mnożenia zajmuje pewna funkcja binarna na liczbach całkowitych. Dla takich funkcji binarnych należą dominance product, threshold product i odległości l_{2p+1} dla stałego p. Wykorzystując wyżej opisane redukcje, autorzy wykazują równość (z dokładnością do czynników polilogarytmicznych) złożoności wyliczania powyższych funkcji dla dwóch zbiorów wektorów. Dodatkowo, autorzy dowodzą, że APHam (oraz ten sam problem z użyciem innych wymienionych funkcji) mieści się w czasie polilogarytmicznym od mnożenia macierzy rozmiaru n na nd i nd na n, zawierających po nd niezerowych wartości. 
07.11.2018 12:14 Paweł Palenica 
Podstawy Informatyki On Randomised Strategies in the λCalculus by Ugo Dal Lago and Gabriele Vanoni 
In this work we introduce randomized reduction strategies  a notion already studied in the context of abstract reduction systems  for the lambdacalculus. We develop a simple framework that allows us to prove if a probabilistic strategy is positive almostsurely normalizing. Then we propose a simple example of probabilistic strategy for the lambdacalculus that has such a property and we show why it is nontrivial with respect to classical deterministic strategies such as leftmostoutermost or rightmostinnermost. We conclude studying this strategy for two classical sub lambda calculi, namely those duplication and erasure are syntactically forbidden. 
06.11.2018 16:15 Szymon Łukasz 
Algorytmy Randomizowane i Aproksymacyjne NPhardness of coloring 2colorable hypergraph with polylogarithmically many colors (A. Bhangale) 
We give very short and simple proofs of the following statements: Given a 2colorable 4uniform hypergraph on n vertices, 1) It is NPhard to color it with log^delta n colors for some delta>0. 2) It is quasiNPhard to color it with O({log^{1o(1)} n}) colors. 
31.10.2018 12:14 Rafał Burczyński 
Podstawy Informatyki A Hitchhiker’s Guide to descriptional complexity through analytic combinatorics by Sabine Broda, António Machiavelo, Nelma Moreira and Rogério Reis 
Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic averagecase results for several $\epsilonNFA$ constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the $\epsilonNFA$ constructions approaches the corresponding $\epsilonfree NFA$ construction, asymptotically and on average. 
30.10.2018 16:15 Wiktor Daniec 
Algorytmy Randomizowane i Aproksymacyjne David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5) 
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5) 
25.10.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna A new variant of the game of cops and robber 
We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v_{1},v_{2},...,v_{k}} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector D_{u}(B)=(d_{1},_{2},...,d_{k}) whose components d_{i}=d_{G}(u,v_{i}), i=1,2,...,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localise him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤V(G) holds obviously. The aim of the talk is to present results concerning 2trees, outerplanar graphs and planar graphs. This is a joint work with Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, and Małgorzata ŚleszyńskaNowak. 
25.10.2018 14:00 Filip Bartodziej, Vladyslav Hlembotskyi 
Algorytmika Finegrained Lower Bounds on Cops and Robbers 
Sumienni policjanci, czy sprytny złodziej? Na tym seminarium dowiemy się kto triumfuje, jak szybko (lub jak wolno) jesteśmy w stanie się o tym przekonać i ilu policjantów wystarczy, aby przyskrzynić nawet samego Frank’a Abagnale’a. Rozważania bedą oparte o grę strategiczna w policjantów i złodziei na grafie (cops and robbers). Uzyskane wyniki opierają sie na założeniu SETH/ETH. 
24.10.2018 12:14 Szymon Stankiewicz 
Podstawy Informatyki Encoding Turing Machines into the Deterministic Lambda Calculus by Ugo Dal Lago and Beniamino Accattoli 
This note is about encoding Turing machines into the lambda calculus. The encoding we show is interesting for two reasons: 1. Weakly strategy independent : the image of the encoding is a very small fragment of the lambda  calculus, that we call the deterministic lambda calculus det. Essentially, it is the CPS (continuationpassing style) lambda calculus restricted to weak evaluation (i.e., not under abstractions). In det every term has at most one redex, and so all weak strategies collapse into a single deterministic evaluation strategy, because there are no choices between redexes to be made. The important consequence of this property is that every weak evaluation strategy then allows to simulate Turing machines,as well as any strong strategy reducing weak head redexes (or even only weak head redexes) first. 2. Linear overhead: the simulation is very efficient, when taking the number of betasteps as the time cost model for the deterministic lambda calculus. The simulation in det indeed requires a number of betasteps that is linear in the number of transitions of the encoded Turing machine, which is the best possible overhead. Therefore, not only all weak strategies simulate Turing 
18.10.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna Local Dimension is Unbounded for Planar Posets 
In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic DushnikMiller concept of dimension, and establishing links between both parameters and structural graph theory, pathwidth and treewidth in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the treewidth of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter. 
18.10.2018 14:00 Jan Mełech, Rafał Burczyński 
Algorytmika A Simple NearLinear Pseudopolynomial Time Randomized Algorithm for Subset Sum 
Celem znanego problemu NPzupełnego SubsetSum jest znalezienie takiego podzbioru multizbioru o mocy n, którego suma elementów wynosi t. Autorzy prezentują krótkie probabilistyczne rozwiązanie bazujące na szybkiej transformacie Fouriera oraz manipulacjach na funkcjach tworzących działające w czasie O((n+t)*polylog(t)) i zwracające odpowiedź z prawdopodobieństwem błędu rzędu O(1/(n+t)). Ten wynik został osiągnięty wcześniej, jednak praca upraszcza rozwiązanie, zawierając je raptem w kilku stronach. 
17.10.2018 16:15 24.10.2018 16:15 Patryk Mikos 
Informatyka Teoretyczna Does the representation matter? 
The class of unit interval graphs has at least 3 equivalent definitions:
We ask whether the competitive ratio in the online unitinterval graph coloring with bandwidths depends on the chosen graph representation. 
17.10.2018 12:14 Vladyslav Hlembotskyi 
Podstawy Informatyki Limited Automata and Regular Languages by Giovanni Pighizzini and Andrea Pisoni 
Limited automata are onetape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1limited automata and oneway deterministic finite automata. The gap reduces to single exponential in the case of deterministic 1limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1limited automata. Another consequence is that 1limited automata can have less states than equivalent twoway nondeterministic finite automata. We show that this is true even if we restrict to the case of the oneletter input alphabet. For each d \geq 2, dlimited automata are known to characterize the class of contextfree languages. Using the ChomskySchutzenberger representation for contextfree languages,

11.10.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna A Tight Bound for Shortest Augmenting Paths on Trees 
The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound. This is a joint work with Dariusz Leniowski, Piotr Sankowski, and Anna ZychPawlewicz. 
11.10.2018 14:00 Dawid Pyczek, Michał Zieliński 
Algorytmika On the WorstCase Complexity of TimSort 
TimSort jest bardzo interesującym algorytmem sortującym, który został wprowadzony do Pythona stosunkowo niedawno, bo w 2002 roku. Ten bardzo popularny algorytm używany jest z powodzeniem na całym świecie. Wynika to z faktu, że działa on wyjątkowo szybko na częściowo posortowanych danych. Aż do niniejszej pracy nie była znana pesymistyczna złożoność tego algorytmu  w pracy pokazane zostanie, że pesymistyczna złożoność algorytmu TimSort wynosi O(n log n). Następnie złożoność algorytmu ograniczymy przez O(n+n log ρ), gdzie ρ to ilość przebiegów. Pierwsza złożoność w bezpośredni sposob wynika z drugiej, ale oba dowody są ciekawe i pomagają lepiej zrozumieć działanie TimSorta. Dodatkowo w wyniku analizy algorytmu autorzy pracy odryli błąd w implementacji TimSorta w Javie. 
10.10.2018 16:15 Andrzej Dorobisz 
Informatyka Teoretyczna Induced subgraphs of graphs with large chromatic number 
Based on the paper a proof of a 1985 conjecture of Gyarfas that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ will be presented. 
10.10.2018 12:14 Michał Zieliński 
Podstawy Informatyki Lambda Theories allowing Terms with a Finite Number of Fixed Points by BENEDETTO INTRIGILA and RICHARD STATMAN 
A natural question in the lambda calculus asks what is the possible number of fixed points of a combinator (closed term). A complete answer to this question is still missing (Problem 25 of TLCA Open Problems List) and we investigate the related question about the number of fixed points of a combinator in lambdatheories. We show the existence of a recursively enumerable lambda theory where the number is always one or infinite. We also show that there are lambdatheories such that some terms have only two fixed points. In a first example, this is obtained by means of a nonconstructive (more precisely nonr.e.) lambdatheory where the range property is violated. A second, more complex example of a nonr.e. Lambdatheory (with a higher unsolvability degree) shows that some terms can have only two fixed points while the range property holds for every term. 
04.10.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna Some open problems 
03.10.2018 12:14 Jarosław Duda Instytut Informatyki UJ 
Podstawy Informatyki Krótkie wprowadzenie do ANS, MERW i pól Markova 
Na seminarium spróbuję zainteresować kilkoma z tematów, którymi się zajmowałem, np. kodowaniem Asymmetric Numeral Systems, które jest obecnie używane w produktach m.in. Apple, Facebook, Google. Opowiem też o Maximal Entropy Random Walk, czyli jak optymalnie wybierać błądzenie przypadkowe na grafie  z perspektywy zastosowań m.in. do maksymalizacji ilości przechowywanej informacji, zrozumienia i naprawienia rozbieżności między dyfuzją a mechaniką kwantową, analizy obrazów, sieci społecznych, czy rekonstrukcji traktów nerwowych. Tematem łączącym powyższe będą pola Markova, czyli wielowymiarowe uogólnienie procesów Markova, o których też krótko opowiem z przykładem zastosowania do poprawienia pojemności dysków twardych. Slajdy do seminarium można znaleźć na: http://tiny.cc/2jpiyy 
14.06.2018 16:15 Mateusz Twaróg, Patryk Urbański, Łukasz Majcher 
Optymalizacja Kombinatoryczna Progress in the Arachne Project 
13.06.2018 12:14 Marcin Briański 
Podstawy Informatyki COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS by DENIS HIRSCHFELDT, CARL JOCKUSCH, RUTGER KUYPER, AND PAUL SCHUPP 
A coarse description of a set A \subset \omega is a set D \subset \omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1random and B is computable from every coarse description D of A, then B is Ktrivial, which implies that if A is in fact weakly 2random then B is computable. Our main tool is a kind of compactness theorem for coneavoiding descriptions, which also allows us to prove the same result for 1 genericity in place of weak 2randomness. In the other direction, we show that if A \leq_T \emptyset is a 1random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all Ktrivial sets are computable from every coarse description of some 1random set.

07.06.2018 17:15 Krzysztof Maziarz 
Optymalizacja Kombinatoryczna The chromatic number of the plane is at least 5 
The HadwigerNelson problem asks for the minimum number of colors required to color the plane, in such a way, that any two points at distance exactly one are assigned different colors. Albeit its simple definition, no significant progress on the question was made for nearly a century. In the discussed paper, Aubrey D. N. J. de Grey has shown a set of points in the plane, such that 5 colors are necessary to color it properly, thus improving a longstanding lower bound of 4 colors. Interestingly, the smallest such set discovered so far has 1581 vertices. The chromatic number of the plane is at least 5, Aubrey D.N.J. de Grey 
07.06.2018 16:15 Szymon Łukasz 
Optymalizacja Kombinatoryczna Dynamic Ffree Coloring of Graphs 
An Ffree coloring is a coloring of a graph such that each color induces an Ffree graph. In this talk we consider dynamic Ffree coloring which can be interpreted as a game of Presenter and Painter. In each move Presenter presents new vertices along with the edges between them and already known vertices. In the same move Presenter can also discolor arbitrary vertices and request Painter to color some vertices. The problem we consider can be stated as follows: For a given graph G, is there a sequence of moves for which the greedy algorithm uses at least k colors during dynamic Ffree coloring of G. We will show that for some classes of graphs this problem is decidable in polynomial time (for fixed F and k) in the case where F is 2connected or F is path of length 2. Piotr Borowiecki, Elżbieta Sidorowicz, Dynamic Ffree Coloring of Graphs, Graphs and Combinatorics 2018, Volume 34, Issue 3, pp 457475 
06.06.2018 12:14 Bruno Pitrus 
Podstawy Informatyki Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger 
The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tuttestyle topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.

30.05.2018 16:15 06.06.2018 16:15 Grzegorz Herman 
Informatyka Teoretyczna Relational parsing: a clean generalized parsing algorithm. 
We propose a new, worstcase cubictime, generalized parsing algorithm for all contextfree languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (noncanonical) implementations behaves analogously to generalized LL, LeftCorner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures. 
30.05.2018 12:14 Bartłomiej Puget 
Podstawy Informatyki STATMAN'S HIERARCHY THEOREM by BRAM WESTERBAAN, BAS WESTERBAAN, RUTGER KUYPER, CARST TANKINK, REMY VIEHOFF AND HENK BARENDREGT 
In the Simply Typed lambda calculus Statman investigates the reducibility relation between types: for types freely generated using \arrow and a single ground type 0, define A \leq B if there exists a lambda definable injection from the closed terms of type A into those of type B. Unexpectedly, the induced partial order is the (linear) wellordering (of order type) \omega + 4.

24.05.2018 16:15 Marcin Briański 
Optymalizacja Kombinatoryczna How many ants does it take to find the food? 
In this talk we will consider the ANTS (Ants Nearby Treasure Search) problem: consider n agents (ants), controlled by finite automata (or PDAs) exploring an infinite grid attempting to locate a hidden treasure. The question we want to answer is: how many agents are necessary to accomplish this task in (expected) finite time? Of course, the answer will depend on the way we model this situation. We will consider synchronous as well as asynchronous environment, agents with access to randomness as well as deterministic ones, agents controlled by PDA as well as finite automata and various combinations thereof. In most cases established bounds are tight, however in certain cases there is still ample room for improvement (which some might consider interesting). Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, Roger Wattenhofer, How many ants does it take to find the food?, Theoretical Computer Science Volume 608, Part 3, 10 December 2015, Pages 255267 
23.05.2018 12:14 
Podstawy Informatyki Canceled 
17.05.2018 16:15 Marcin Muszalski 
Optymalizacja Kombinatoryczna On the Number of Maximum Empty Boxes Amidst n Points 
I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant): 
16.05.2018 12:14 Maciej Czerwiński 
Podstawy Informatyki On Type Inference in the Intersection Type Discipline by Gerard Boudol and Pascal Zimmer 
We introduce a new unification procedure for the type inference problem in the intersection type discipline. We show that unification exactly corresponds to reduction in an extended lambda calculus, where one never erases arguments that would be discarded by ordinary βreduction. We show that our notion of unification allows us to compute a principal typing for any strongly normalizing lambda expression. 
10.05.2018 16:15 Jakub Szarawski 
Optymalizacja Kombinatoryczna Faster approximation schemes for the twodimensional knapsack problem 
In 2008 Klaus Jansen and Roberto SolisOba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented. 
09.05.2018 12:14 Dominika Salawa 
Podstawy Informatyki The Hiring Problem and Permutations by Margaret Archibald and Conrado Martínez 
The hiring problem has been recently introduced by Broder et al. in last year’s ACMSIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem. 
26.04.2018 16:15 Sylwester Klocek 
Optymalizacja Kombinatoryczna Colouring of (P3∪P2)free graphs 
In a paper authors are colouring of (P3∪P2)free graphs, a super class of 2K2 free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) free graphs, and sharper bounds for (P3∪P2 , diamond)free graphs and for (2K2, diamond)free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs. Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)free graphs, Graphs and Combinatorics, Volume 34 (1), 2018 
25.04.2018 16:15 Jacek Krzaczkowski 
Informatyka Teoretyczna Complexity of solving equations 
Solving equations is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is obviously decidable in nondeterministic polynomial time. The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on the polynomial equivalence problem in which we ask whether two polynomials over a finite algebra describe the same function. This is joint work with Paweł M. Idziak and Piotr Kawałek.. 
25.04.2018 12:00 Rafał Burczyński 
Podstawy Informatyki How to select a loser 
Consider the following game: everyone from a group of n people flips a coin with result either 0 or 1, both equally probable; if no one gets a 0, the round is repeated, otherwise people with 1's are considered "winners" and the game continues only with participants who got 0's. The process continues until there is one person left, who is called "loser". We can picture this process as a binary tree and analyze some of its properties in average case. The analysis is not completely trivial, in particular one may find application for tools such as Mellin transform. 
19.04.2018 16:15 Grzegorz Jurdziński 
Optymalizacja Kombinatoryczna Split Packing: An Algorithm for Packing Circles with Optimal WorstCase Density 
Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NPhard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constantfactor approximation algorithm for the problem of finding a smallest square which can fit given circles. 
18.04.2018 12:00 Rafał Burczyński 
Podstawy Informatyki Mellin transforms and asymptotics 
We will introduce Mellin transform, which may be used for the asymptotic analysis of a particular class of sums. I will start with basic properties and then present fundamental correspondence between the asymptotic expansion of a function at 0 or infinity and singularities of its transform. Finally we will show some combinatorial applications of the transform. 
12.04.2018 16:15 Maciej Woźniak 
Optymalizacja Kombinatoryczna Find Your Place: Simple Distributed Algorithms for Community Detection 
Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if:
We define (weak) block reconstruction of graph as twocoloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact. I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for nonregular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities. 
11.04.2018 12:14 Weronika Grzybowska 
Podstawy Informatyki Average complexity of Moore’s and Hopcroft’s algorithms by Julien David 
In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore’s state minimization algorithm is O(n log (log n)), where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hopcroft’s algorithm is characterized, for which the algorithm will be proved to be always faster than Moore’s algorithm. Finally, we present experimental results on the usual implementations of Hopcroft’s algorithm. 
05.04.2018 16:15 Anna Kobak 
Optymalizacja Kombinatoryczna On treepartitionwidth 
A treepartition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a treepartition is the maximum number of vertices in a bag. The treepartitionwidth of G is the minimum width of a treepartition of G. I will prove three theorems presented in the article, showing an upper bound on the treepartitionwidth of all graphs, a lower bound for chordal graphs and a lower bound for graphs with treewidth 2. 
04.04.2018 16:15 Bartosz Walczak 
Informatyka Teoretyczna Sparse Kneser graphs are Hamiltonian 
For integers Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636). 
04.04.2018 12:14 Vladyslav Hlembotskyi 
Podstawy Informatyki A graph theoretic approach to automata minimality by Antonio Restivo and Roberto Vaglica 
The paper presents a graphtheoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graphtheoretic terms. 
28.03.2018 16:15 Grzegorz Guśpiel 
Informatyka Teoretyczna On the Complexity of Crossing Minimization 
For a bipartite graph G with vertex bipartition (X, Y), a twolayer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines L_{X} and L_{Y}, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a twolayer drawing is a twolayered graph. We study basic graph problems on twolayered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.
This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi. 
28.03.2018 12:00 Szymon Stankiewicz 
Podstawy Informatyki Introduction to HigherOrder Categorical Logic  continuation 
22.03.2018 16:15 Aleksandra Mędrek 
Optymalizacja Kombinatoryczna The Matching Problem in General Graphs is in QuasiNC 
Authors show that the perfect matching problem in general graphs is in quasiNC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasiNC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached. Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in QuasiNC, FOCS 2017 
21.03.2018 12:00 Szymon Stankiewicz 
Podstawy Informatyki Introduction to HigherOrder Categorical Logic by Lambec and Scott 
15.03.2018 16:15 Dawid Pyczek 
Optymalizacja Kombinatoryczna Punctured combinatorial Nullstellensätze 
This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problemsolving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions. 
14.03.2018 16:15 Michael Kompatscher Charles University in Prague 
Informatyka Teoretyczna CSPs of infinite structures and equations in oligomorphic algebras 
In 1998 Feder and Vardi famously conjectures that the constraint satisfaction problem (CSP) of a finite structure is either in P or NPcomplete. Universal algebra turned out to be the main tool in tackling their conjecture and lead to two recent proofs, showing that CSP(A) is in P if the polymorphism algebra associated with A is a Taylor algebra, and NPcomplete otherwise.
For CSPs of structures with infinite domains this universal algebraic approach fails badly in general. However, if the automorphism group of the structure is "sufficiently big", i.e. oligomorphic, many results can be transferred from the finite case. We survey results about the equational structure of oligomorphic algebras and their applications to constraint satisfaction problems. 
14.03.2018 12:14 Dawid Pyczek i Jakub Rówiński 
Podstawy Informatyki Asymptotic Density and the Theory of Computability by CARL JOCKUSCH AND PAUL SCHUPP 
The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few easy proofs to illustrate the flavor of the subject. In complexity theory, classes such as P and NP are defined by using worstcase measures. That is, a problem belongs to the class if there is an algorithm solving it which has a suitable bound on its running time over all instances of the problem. Similarly, in computability theory, a problem is classified as computable if there is a single algorithm which solves all instances of the given problem. There is now a general awareness that worstcase measures may not give a good picture of a particular algorithm or problem since hard instances may be very sparse. The paradigm case is Dantzig’s Simplex Algorithm for linear programming problems. This algorithm runs many hundreds of times every day for scheduling and transportation problems, almost always very quickly. There are clever examples of Klee and Minty showing that there exist instances for which the Simplex Algorithm must take exponential time, but such examples are not encountered in practice. Observations of this type led to the development of averagecase complexity by Gurevich and by Levin independently. There are different approaches to the averagecase complexity, but they all involve computing the expected value of the running time of an algorithm with respect to some measure on the set of inputs. Thus the problem must be decidable and one still needs to know the worstcase complexity. Another example of hard instances being sparse is the behavior of algorithms for decision problems in group theory used in computer algebra packages. There is often some kind of an easy “fast check” algorithm which quickly produces a solution for “most” inputs of the problem. This is true even if the worstcase complexity of the particular problem is very high or the problem is even unsolvable. Thus many grouptheoretic decision problems have a very large set of inputs where the (usually negative) answer can be obtained easily and quickly. 
20.06.2018 12:15 Wojciech Szpankowski Purdue University USA 
Podstawy Informatyki Analytic Information Theory: From Shannon to Knuth and Back 
08.03.2018 16:15 Jakub Rówiński 
Optymalizacja Kombinatoryczna On the 1/3–2/3 Conjecture 
Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an αbalanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams. Emily J. Olson, Bruce E. Sagan, On the 1/32/3 Conjecture, Order, 2018 
07.03.2018 12:14 Jarosław Duda Instytut Informatyki UJ 
Podstawy Informatyki Some nonstandard approaches to hard computational problems 
I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm, compressed sensing, and the problem with global optimization formulations used in adiabatic
Slides: https://tinyurl.com/y74nx2t6 
01.03.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna Some open problems 
28.02.2018 16:15 Piotr Micek 
Informatyka Teoretyczna Seymour's conjecture on 2connected graphs of large pathwidth 
We prove the conjecture of Seymour (1993) that for every apexforest H1 and outerplanar graph H2 there is an integer p such that every 2connected graph of pathwidth at least p contains H1 or H2 as a minor. This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood. 
25.01.2018 16:15 Bartłomiej Bosek 
Optymalizacja Kombinatoryczna News about Combinatorial Nullstellensatz 
I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems. 
18.01.2018 16:15 Jarek Duda 
Optymalizacja Kombinatoryczna Some nonstandard approaches to hard computational problems 
I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subsetsum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem. Jarek Duda. Some unusualapproaches to hard computational problems. slides. 
17.01.2018 16:15 24.01.2018 16:15 Andrzej Dorobisz 
Informatyka Teoretyczna Online bipartite matching with amortized O(log²n) replacements 
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound. The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].
Based on the paper: Online bipartite matching with amortized O(log²n) replacements by Aaron Bernstein, Jacob Holm and Eva Rotenberg 
17.01.2018 12:00 Bartłomiej Puget i Dominika Salawa 
Podstawy Informatyki Chapters 8.5  8.9 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
11.01.2018 16:15 Maciej Woźniak, Dawid Pyczek 
Optymalizacja Kombinatoryczna Online Vertex Cover and Matching: Beating the Greedy Algorithm 
Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal waterfilling algorithm with competitive ratio 1/(11/e) . The main contribution of this paper is a 1.901competitive algorithm for vertex cover in general graphs which beats the wellknown trivial 2competitive algorithm. The next major result is a primaldual analysis of given algorithm that implies the dual result of a 0.526competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs. 
10.01.2018 12:00 Kamil Rajtar 
Podstawy Informatyki Chapters 8.1  8.4 of AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS by Robert Sedgewick, Philippe Flajolet 
04.01.2018 16:15 Grzegorz Bukowiec 
Optymalizacja Kombinatoryczna Feedback Vertex Set Problem 
A Feedback Vertex Set (FVS) is a subset of vertices in a graph such that its removal results in an acyclic graph. The problem of finding a minimal FVS is one of the classic NPcomplete problems. However, in some practical cases, we can assume that its size is fairly small. This motivated an intensive study of the parametrized version of this problem, which asks either for FVS of a size at most k or an information that it doesn't exist. There are several deterministic algorithms known which solve this in time O^{*}(c^{k}), the best one for now being O^{*}(3.592^{k}). 
 Strona Główna
 Katedra Algorytmiki
 Katedra Podstaw Informatyki
 Wydział Matematyki i Informatyki
 Kontakt
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Galeria
 Ludzie
 Maciej Bendkowski
 Bartłomiej Bosek
 Iwona Cieślik
 Piotr Danilewski
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Tomasz Kisielewski
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Łukasz Lachowski
 Agnieszka Łupińska
 Grzegorz Matecki
 Piotr Micek
 Patryk Mikos
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Maciej Ślusarek
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Byli współpracownicy