Kraków, Poland, May 11–12, 2018
FIT (Forum Informatyki Teoretycznej) is a Polish theoretical computer science meeting organized on a yearly basis since 1991. This year the meeting will take place in Kraków on Friday, May 11, and Saturday, May 12, and is organized by the Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University.
Günter Rote, Freie Universität Berlin
Standa Živný, University of Oxford
10:00 Invited Lecture
Günter Rote (Freie Universität Berlin)
Minimal dominating sets in trees: counting, enumeration, and extremal results
A tree with $n$ vertices has at most $95^{n/13}$ minimal dominating sets. The corresponding growth constant $95^{1/13}\approx 1.4194908$ is best possible.
I will show how these results are obtained in a semi-automatic way with computer help, starting from the dynamic-programming recursion for computing the number of minimal dominating sets of a given tree. This recursion defines a bilinear operation on sixtuples, and the growth constant arises as a kind of "dominant eigenvalue" of this operation.
We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between reporting successive solutions. It is open whether the delay can be reduced to a constant delay, for an appropriate modification of the problem statement.
11:00 Coffee Break
11:30 Contributed Talks
Marcin Pilipczuk (University of Warsaw)
Recent progress in distance and cut sparsifiers
In the talk I will discuss two related notions with regards to graph compression.
In many special cases, the known upper and lower bounds for the above concepts are surprising far from each other. In the talk, I will survey these areas, with emphasize on open problems. Furthermore, I will present our recent result obtained in a joint work with Nikolai Karpov and Anna Zych-Pawlewicz, namely an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with $k$ terminals that require $2^{k−2}$ edges in any mimicking network.
Krzysztof Kiljan (University of Warsaw)
Experimental evaluation of parameterized algorithms for Feedback Vertex Set
Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of view of parameterized algorithms and fixed-parameter tractability, Feedback Vertex Set is one of the landmark problems: a long line of study resulted in multiple algorithmic approaches and deep understanding of the combinatorics of the problem. Because of its central role in parameterized complexity, the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured Feedback Vertex Set as the problem of choice in one of its tracks.
The results of PACE 2016 on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. In this talk we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.
Michał Ziobro (Jagiellonian University)
Finding Hamiltonian cycle in graphs of bounded treewidth: experimental evaluation
The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be swept with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm.
In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., $2^{O(t)}$) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., $2^{O(t\log t)}$) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle.
Mateusz Lewandowski (University of Wrocław)
Approximating node-weighted k-MST on planar graphs
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+\varepsilon)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al. (SWAT’16) and adopting an approach by Chudak et al. (Math. Prog. ’04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. ’06).
More generally, our approach readily gives a $(4/3\cdot r+\varepsilon)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Könemann et al. (Algorithmica ’11) for partial cover problems. Together with a lower bound construction by Mestre (STACS’08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a non-black-box fashion could not beat the factor $4/3\cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
Katarzyna Paluch (University of Wrocław)
New approximation algorithms for (1,2)-TSP
We give faster and simpler approximation algorithms for the $(1,2)$-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either $1$ or $2$.
Our main results are two approximation algorithms for $(1,2)$-TSP, one with approximation factor $8/7$ and run time $O(n^3)$ and the other having an approximation guarantee of $7/6$ and run time $O(n^{2.5})$. The $8/7$-approximation matches the best known approximation factor for $(1,2)$-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of $O(n^9)$. Thus, ours is the first improvement for the $(1,2)$-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an $8/7$-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best $8/7$-approximation.
The $7/6$-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.
Karol Węgrzycki (University of Warsaw)
Subquadratic approximation scheme for Partition
The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an $O((n+1/\varepsilon)^{5/3})$ time randomized FPTAS for Partition, which is derived from a certain relaxed form of a randomized FPTAS for Subset Sum. To the best of our knowledge, this is the first NP-hard problem that has been shown to admit a subquadratic time approximation scheme, i.e., one with time complexity of $O((n+1/\varepsilon)^{2-\delta})$ for some $\delta>0$. To put these developments in context, note that a quadratic FPTAS for Partition has been known for 40 years.
Our main contribution lies in designing a mechanism that reduces an instance of Subset Sum to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics.
We also prove several related results. Notably, we improve approximation schemes for 3SUM, $(\min,+)$-convolution, and Tree Sparsity. Finally, we argue why breaking the quadratic barrier for approximate Knapsack is unlikely by giving an $\Omega((n+1/\varepsilon)^{2-o(1)})$ conditional lower bound.
13:00 Lunch
14:15 Contributed Talks
Łukasz Jeż (University of Wrocław)
Make-to-order integrated scheduling and distribution
Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.
Artur Kraska (University of Wrocław)
Deterministic online matching with delays
We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) introduced by Emek et al. (STOC 2016). In this problem, an even number of requests appear in a metric space at different times and the goal of an online algorithm is to match them in pairs. In contrast to traditional online matching problems, in MPMD all requests appear online and an algorithm can match any pair of requests, but such decision may be delayed (e.g., to find a better match). The cost is the sum of matching distances and the introduced delays. We present the first deterministic solutions for this problem.
Marcin Dziubiński (University of Warsaw)
Hide and seek games with multiple seeking resources
Hide and seek games, introduced by John von Neumann, are among the oldest classes of games studied in game theory. These games are closely related to security games, studied extensively in artificial intelligence, and are an example of conflicts with multiple battlefields with discrete resources. We will present analytical characterization of equilibria of these games and show how it can be used to improve existing algorithms for finding equilibria in such games.
Piotr Skowron (University of Warsaw)
A quantitative analysis of multi-winner rules
To choose a suitable multi-winner rule, i.e., a voting rule for selecting a subset of $k$ alternatives based on a collection of preferences, is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset. In this paper, we offer a new perspective to measure the quality of such subsets and – consequently – multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the (Approval) Chamberlin–Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.
Michał Seweryn (Jagiellonian University)
The dimension of posets with excluded minors in cover graphs
A fan is a graph obtained from a path by adding an extra vertex adjacent to all vertices on the path. We give a qualitative structure theorem for graphs excluding a fan as a minor. This is inspired by a recent result by Ding that gives an approximate description of graphs excluding $K_{2,n}$ as a minor. Next, we use both characterizations to show that the dimension of a poset is bounded in terms of the size of a largest $K_{2,n}$ or a fan (graph) which is a minor of the cover graph. This is a step towards characterization of minor-closed graph classes such that posets with cover graphs from such a class have bounded dimension.
Adam Polak (Jagiellonian University)
Tight conditional lower bounds for Longest Common Increasing Subsequence
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called $k$-LCIS: Given $k$ integer sequences $X_1,\ldots,X_k$ of length at most $n$, the task is to determine the length of the longest common subsequence of $X_1,\ldots,X_k$ that is also strictly increasing. Especially for the case of $k=2$ (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case.
Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound (1) to rule out $O((nL)^{1-\varepsilon})$ time algorithms for LCIS, where $L$ denotes the solution size, (2) to rule out $O(n^{k-\varepsilon})$ time algorithms for $k$-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.
This is joint work with Lech Duraj and Marvin Künnemann, presented at IPEC 2017.
15:45 Coffee Break
16:15 Contributed Talks
Tomasz Kociumaka (University of Warsaw)
Local consistence in data structures for text processing
Locally consistent parsing is a common name for a family of schemes which build a parse tree over the input text so that any two equal fragments are parsed in essentially the same way. Several constructions, including the original one by Sahinalp and Vishkin and the much more recent recompression by Artur Jeż, appear in state-of-the-art solutions to many problems of text algorithms: in compressed pattern matching, dynamic indexing, word equations, and more. At SODA 2015, with J. Radoszewski, W. Rytter and T. Waleń, we introduced a related notion of locally consistent representative assignment in order to design efficient data structures for internal queries – questions concerning fragments of a static text. For example, the periods of any fragment of a length-$n$ text can be retrieved in $O(\log n)$ time using our linear-size data structure.
In the talk, I will report a new discovery concerning the fundamental LCE queries, which ask for the longest common prefix of any two fragments. For a text of length $n$, the textbook solutions, based on the suffix tree or the suffix array, take $O(n\log n)$ bits even if the alphabet size $\sigma$ is constant. Local consistency lets us achieve for the first time the optimal space of $O(n\log\sigma)$ bits while preserving $O(1)$ query time. Moreover, our data structure can be constructed deterministically in $O(n\log\sigma/\log n)$ time provided that $\Theta(\log_\sigma n)$ characters are packed in each machine word representing the input text.
Grzegorz Herman (Jagiellonian University)
Relational parsing: a clean generalization of GLL, GLC, and GLR
We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free 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 (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.
Jan Wróblewski (University of Warsaw)
Strong invariants and static typing of dynamic languages
Introducing static typing to dynamic languages (such as Python or JavaScript) is an active research field which can produce better IDEs and improve Just-In-Time compilers for these languages. However, construction of a type system for mainstream dynamic languages that feature runtime object modification requires solution to multiple undecidable subproblems. The main reason is that even computing the validity of usage of a dot operator (object.property
) requires information whether the property was assigned to the object during the runtime (object.property := value
), which in turn requires full alias analysis of the program (which is undecidable).
My approach to this problem is introduction of strong invariants to a type system of such a language. These strong invariants are used to check at runtime whether some basic properties are satisfied (e.g., a property of an object is not modified or removed throughout the evaluation of an expression), and give the type system additional information to work with. I will describe the ideas behind this approach on a small dynamic language that models most essential features of the Python language.
Piotr Danilewski (Jagiellonian University)
Dynamic Staging: compile-time, run-time, or any other time
Staging in programming languages is a mechanism that allows for partial execution of a program in multiple phases. Each phase produces a new code that is specialized with respect to some parameters. Typical phases are compile-time and run-time evaluation, but there can be more.
In this talk, we present our approach to staging. Formally, it is a small extension to lambda calculus. Practically, it provides a first-class entity that can be used to control the order of execution and trigger multiple stages at the programmer's will. The staging can be parametrized, and the same code can be reused between stages or be specialized in a different way.
We show a few practical examples, as well as how dynamic staging fits in our bigger project: ManyDSL.
Piotr Ostropolski-Nalewaja (University of Wrocław)
Can one escape red chains? Regular Path Queries Determinacy is undecidable.
For a given set of queries (which are expressions in some query language) $\mathcal{Q}=\{Q_1,Q_2,\ldots,Q_k\}$ and for another query $Q_0$ we say that $\mathcal{Q}$ determines $Q_0$ if – informally speaking – for every database $\mathbb{D}$, the information contained in the views $\mathcal{Q}(\mathbb{D})$ is sufficient to compute $Q_0(\mathbb{D})$.
Query Determinacy Problem is the problem of deciding, for given $\mathcal{Q}$ and $Q_0$, whether $\mathcal{Q}$ determines $Q_0$. Many versions of this problem, for different query languages, were studied in database theory. In this paper we solve a problem stated in [CGLV02] and show that Query Determinacy Problem is undecidable for the Regular Path Queries – the paradigmatic query language of graph databases.
Radosław Piórkowski (University of Warsaw)
Petri nets with data – WQO Dichotomy Conjecture
Decidability of many standard decision problems for Petri nets becomes an open problem once we extend the model with data. If we restrict only to homogeneous data domains, according to the WQO Dichotomy Conjecture there exists a simple criterion for decidability. I will introduce the model of Petri nets with data, state the conjecture and say what is currently known about it.
17:45 Information about the Polish Chapter of the ACM
Jarosław Byrka (University of Wrocław)
18:00 Break
19:00 Conference Dinner
10:00 Invited Lecture
Standa Živný (University of Oxford)
CSP and friends
We survey algorithmic and complexity results on Constraint Satisfaction Problems (CSPs) and related computational problems. In particular, we discuss various dichotomy results and characterisations of power of algorithms.
11:00 Coffee Break
11:30 Contributed Talks
Emanuel Kieroński (University of Wrocław)
Finite satisfiability of the unary negation fragment with transitivity
Unary negation fragment of first-order logic, UNFO, has been recently introduced by ten Cate and Segoufin. It turns out to have good algorithmic and model-theoretic properties, including decidability of the satisfiability problem and the finite model property. At the same time, its expressive power is quite attractive. In particular it embeds propositional (multi)-modal logic and unions of conjunctive queries.
In this talk we consider an extension of UNFO in which arbitrarily many binary symbols may be required to be interpreted either as equivalence relations or as arbitrary transitive relations. We show that in both cases the satisfiability and the finite satisfiability problem remain decidable and that the variant with equivalences retains the finite model property.
Piotr Kawałek (Jagiellonian University)
Satisfiability of circuits over nilpotent algebras and its application
Satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted for example either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. This in turn 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. The last problem has been shown to be undecidable, however in finite realms such problems are obviously decidable in nondeterministic polynomial time.
A project of characterizing finite algebras $\mathbb{A}$ with polynomial time algorithms deciding satisfiability of circuits over $\mathbb{A}$ has been undertaken in [P. M. Idziak and J. Krzaczkowski, Satisfiability in multi-valued circuits, LICS 2018]. Unfortunately that paper leaves a gap for nilpotent but not supernilpotent algebras. In my talk I will discuss a class of nilpotent algebras, for which the problem is tractable in polynomial time. I will also show how those results could be applied to analyze 3-SAT formulas.
Bartek Klin (University of Warsaw)
Mu-calculus with atoms
We extend the modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, but satisfiability becomes undecidable. We also show expressive limitations of atom-enriched $\mu$-calculi, and explain how their expressive power depends on the structure of atoms used, and on the choice between basic or vectorial syntax.
Piotr Witkowski (University of Wrocław)
Two-variable logic with counting in forests: new results
Algorithms that decide satisfiability problem for extensions of the two variable logic with counting quantifiers (C2 for short) can be quite involved. One not only has to take care to construct a model of C2 formula, but also to impose appropriate interpretation of distinguished symbols (mother-daughter relations in forests, successors of linear orders, equivalence relations etc.). Resulting proofs become technically challenging and the essence of reasoning is lost in technical details. To cope with this problem we introduce a black-box technique, a method that reduces satisfiability problem for an extension of C2 to a weaker extension of C2, or even to C2 itself. With this method we show that the finite satisfiability for C2 with two independent unranked unordered forests is NEXPTIME-complete, and that the (general) satisfiability problem for C2 with a single forest is also NEXPTIME-complete.
Grzegorz Madejski (University of Gdańsk)
Membership problem for two-dimensional jumping finite automata
Jumping automata caught a lot of attention in the past few years and were considered in numerous papers [4, 1]. The head of a jumping automaton does not read the input word from left to right like in a classical finite automaton, but jumps nondeterministically to arbitrary positions in the word to read and delete parts of it.
Recently, two-dimensional row jumping finite automata were introduced as an interesting computational model for accepting two-dimensional languages [2]. These automata are nondeterministic. They guess an order in which rows of the input array are read and they jump to the next row only after reading all symbols in the previous row. In each row, they use a jumping mode to read and erase segments of the row.
We present our results regarding the membership problem for these automata [3]. We show that each row jumping finite automaton can be simulated by a nondeterministic Turing machine with space bounded by the logarithm. This means that the fixed membership problems for such automata are in P. On the other hand, we show that the uniform membership problem is NP-complete.
References:
Jakub Michaliszyn (University of Wrocław)
Towards learning weighted automata
I will discuss the recent results on weighted automata (where weights are aggregated using functions like sum or average) under probabilistic semantics, including computing the expected value and the cumulative distribution of a given automaton w.r.t. word distribution given by a Markov chain. These results can be applied to approximately determinise weighted automata and shed some light on the weighted automata learning problem.
13:00 Lunch
14:00 Contributed Talks
Tomasz Wąs (University of Warsaw)
Axiomatization of the PageRank centrality
We propose an axiomatization of PageRank. Specifically, we introduce five simple axioms – Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node – and show that PageRank is the only centrality measure that satisfies all of them. Our axioms give new conceptual and theoretical underpinnings of PageRank and show how it differs from other centralities.
Jadwiga Sosnowska (University of Warsaw)
Path evaluation and centralities in weighted graphs – an axiomatic approach
We study the problem of extending the classic centrality measures to weighted graphs. Unfortunately, in the existing extensions, paths in the graph are evaluated solely based on their weights, which is a restrictive and undesirable assumption for a variety of settings. Given this, we define a notion of the path evaluation function that assesses a path between two nodes by looking not only on the sum of edge weights, but also on the number of intermediaries. Using an axiomatic approach, we propose three classes of path evaluation functions. Building upon this analysis, we present the first systematic study how classic centrality measures can be extended to weighted graphs while taking into account an arbitrary path evaluation function. As an application, we use the newly-defined measures to identify the most well-linked districts in a sample public transport network.
Oskar Skibski (University of Warsaw)
Centralities4Cities: centrality measures for public transport networks
I will present how centrality measures can be used for the advanced analysis of public transport networks. In particular, it allows to answer questions such as "how to identify the most well-linked district in Kraków" or "which bus stop have the best direct connections to other parts of the city".
Tomasz Jurdziński (University of Wrocław)
MST in O(1) rounds of Congested Clique
We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in $O(1)$ rounds, with high probability, in the Congested Clique model. The input graph in the Congested Clique model is a graph of $n$ nodes, where each node initially knows only its incident edges. The communication graph is a clique with limited edge bandwidth: each two nodes (not necessarily neighbours in the input graph) can exchange $O(\log n)$ bits.
As in previous works, the key part of the MST algorithm is an efficient Connected Components (CC) algorithm. However, unlike the former approaches, we do not aim at simulating the standard Borůvka algorithm, at least at initial stages of the CC algorithm. Instead, we develop a new technique which combines partitions of sample sparse subgraphs of the input graph in order to accelerate the process of uncovering connected components of the original input graph. More specifically, we develop a sparsification technique which reduces an initial CC problem in $O(1)$ rounds to its two restricted instances. The former instance has a graph with maximal degree $O(\log\log n)$ as the input – here our sample-combining technique helps. In the latter instance, a partition of the input graph into $O(n/\log\log n)$ connected components is known. This gives an opportunity to apply previous algorithms to determine connected components in $O(1)$ rounds.
Our result improves over previous $O(\log^* n)$ algorithm of Ghaffari et al. [PODC 2016], $O(\log\log\log n)$ algorithm of Hegeman et al. [PODC 2015] and the $O(\log\log n)$ algorithm of Lotker et al. [SPAA 2003; SICOMP 2005]. It also determines $\Theta(1)$ round complexity in the congested clique for MST, as well as other graph problems, including bipartiteness, cut verification, $s$–$t$ connectivity, cycle containment and $O(\log\Delta)$ round complexity of the maximal independent set (MIS).
Michał Różański (University of Wrocław)
Deterministic communication in ad hoc wireless networks
We consider deterministic distributed communication in wireless ad hoc networks of identical devices in the SINR model without predefined infrastructure. Most algorithmic results in this model rely on various additional features or capabilities, e.g., randomization, access to geographic coordinates, power control, or carrier sensing. We develop a deterministic clustering algorithm, which splits the nodes of the network into groups such that each group is contained in an area of fixed diameter, and there are $O(1)$ groups in any area of constant diameter. Then, we use the clustering algorithm to accomplish broadcast and local broadcast in the network. Our solution relies on a new type of combinatorial structures, which might be of independent interest.
Grzegorz Stachowiak (University of Wrocław)
Fast space optimal leader election in population protocols
This work was done in collaboration with Leszek Gąsieniec from the University of Liverpool.
The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of $n$ agents.
The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time $O(\log^2 n)$ equivalent to $O(n\log^2 n)$ sequential pairwise interactions, in which each agent utilises $O(\log\log n)$ states. This double logarithmic space utilisation matches asymptotically the lower bound $\frac{1}{2}\log\log n$ on the number of states utilised by agents in any leader election algorithm with the running time $o(n/\operatorname{polylog}n)$, see [AA+17].
15:30 End of Program
The conference will be held in Przegorzały Guesthouse of the Jagiellonian University (Jodłowa 13, Kraków). The guesthouse is located 6 km away from the city center and 9 km from Kraków-Balice Airport.
Public transportation connections – destination stop "Przegorzały UJ":
Important information: Due to construction works, many long-distance trains through Kraków do not stop at the main railway station, but only at the station Kraków Płaszów. Please check the exact route of your train.
We recommend conference participants to book their accommodation in the Przegorzały Guesthouse, where the conference will be held. See the information folder or take a virtual tour. Prices per night with breakfast:
Book via email to halina.zabczynska@uj.edu.pl. Pay on arrival by cash or credit card.
Online registration is closed. Please contact the organizers if you need to modify your data or you would like to participate but have not registered.
Registration fee – 200 PLN. It covers participation in all sessions and invited talks, conference dinner on Friday, lunches on Friday and Saturday, and coffee breaks. The fee does not cover accommodation, which must be booked separately (see above).
Pay your registration fee by May 4 via bank transfer:
IBAN: PL61124047221111000048604116
BIC: PKOPPLPW
Account owner: Uniwersytet Jagielloński, Gołębia 24, 31-007 Kraków
Payment title: FIT + the last name(s) of the participant(s)
Marek Adamczyk (University of Warsaw)
Maciej Bendkowski (Jagiellonian University)
Marcin Bieńkowski (University of Wrocław)
Marcin Briański (Jagiellonian University)
Jarosław Byrka (University of Wrocław)
Piotr Danilewski (Jagiellonian University) (talk)
Lech Duraj (Jagiellonian University)
Stefan Dziembowski (University of Warsaw)
Marcin Dziubiński (University of Warsaw) (talk)
Piotr Faliszewski (AGH University of Science and Technology)
Grzegorz Głuch (University of Wrocław)
Grzegorz Herman (Jagiellonian University) (talk)
Paweł Idziak (Jagiellonian University)
Łukasz Jeż (University of Wrocław) (talk)
Tomasz Jurdziński (University of Wrocław) (talk)
Piotr Kawałek (Jagiellonian University) (talk)
Emanuel Kieroński (University of Wrocław) (talk)
Krzysztof Kiljan (University of Warsaw) (talk)
Bartek Klin (University of Warsaw) (talk)
Tomasz Kociumaka (University of Warsaw) (talk)
Jakub Kozik (Jagiellonian University)
Marcin Kozik (Jagiellonian University)
Artur Kraska (University of Wrocław) (talk)
Tomasz Krawczyk (Jagiellonian University)
Mateusz Lewandowski (University of Wrocław) (talk)
Hsiang-Hsuan Liu (University of Wrocław)
Grzegorz Madejski (University of Gdańsk) (talk)
Jan Marcinkowski (University of Wrocław)
Jerzy Marcinkowski (University of Wrocław)
Krzysztof Maziarz (Jagiellonian University)
Syed Mohammad Meesum (University of Wrocław)
Piotr Micek (Jagiellonian University)
Jakub Michaliszyn (University of Wrocław) (talk)
Patryk Mikos (Jagiellonian University)
Anna Nenca (University of Gdańsk)
Damian Niwiński (University of Warsaw)
Piotr Ostropolski-Nalewaja (University of Wrocław) (talk)
Jan Otop (University of Wrocław)
Leszek Pacholski (University of Wrocław)
Katarzyna Paluch (University of Wrocław) (talk)
Roman Pielka (unaffiliated)
Marcin Pilipczuk (University of Warsaw) (talk)
Radosław Piórkowski (University of Warsaw) (talk)
Adam Polak (Jagiellonian University) (talk)
Günter Rote (Freie Universität Berlin) (invited lecture)
Michał Różański (University of Wrocław) (talk)
Paweł Schmidt (University of Wrocław)
Michał Seweryn (Jagiellonian University) (talk)
Oskar Skibski (University of Warsaw) (talk)
Piotr Skowron (University of Warsaw) (talk)
Jadwiga Sosnowska (University of Warsaw) (talk)
Grzegorz Stachowiak (University of Wrocław) (talk)
Juliusz Straszyński (University of Warsaw)
Andrzej Szepietowski (University of Gdańsk)
Maciej Ślusarek (Jagiellonian University)
Lidia Tendera (University of Opole)
Bartosz Walczak (Jagiellonian University)
Tomasz Wąs (University of Warsaw) (talk)
Karol Węgrzycki (University of Warsaw) (talk)
Piotr Witkowski (University of Wrocław) (talk)
Michał Wrona (Jagiellonian University)
Jan Wróblewski (University of Warsaw) (talk)
Marek Zaionc (Jagiellonian University)
Michał Ziobro (Jagiellonian University) (talk)
Standa Živný (University of Oxford) (invited lecture)
Organizing committee: Maciej Bendkowski, Jakub Kozik, Bartosz Walczak
Email: fit@tcs.uj.edu.pl