FI_t 2022

The aim of this talk is to present a gentle introduction to deep neural networks, with the particular attention on image processing. We start with a brief description on biological neural networks. Next we proceed to the construction of basic artificial neural networks. We follow with the description of convolutional architecture and style transfer for images. Next we present GAN model and the art generated with its application. Finally, we present the denoising autoencoder and its application to diffusion models, which allows the text-to-image generation. We finish with the short discussion on the future on neural networks.

We consider the problem of deciding whether a given pushdown system all of whose ε-transitions are deterministic is weakly bisimulation finite, that is, whether it is weakly bisimulation equivalent to a finite system. We prove that this problem is 2-EXPTIME-complete. This consists of three elements: First, we prove that the smallest finite system that is weakly bisimulation equivalent to a fixed pushdown system, if exists, has size at most doubly exponential in the description size of the pushdown system. Second, we propose a fast algorithm deciding whether a given pushdown system is weakly bisimulation equivalent to a finite system of a given size. Third, we prove 2-EXPTIME-hardness of the problem. The problem was known to be decidable, but the previous algorithm had Ackermannian complexity (6-EXPSPACE in the easier case of pushdown systems without ε-transitions); concerning lower bounds, only EXPTIME-hardness was known.

The talk is based on a paper accepted to SODA 2023, co-authored by Stefan Göller. It is a continuation of our previous paper (LICS 2020), where we showed an 6-EXPSPACE algorithm solving the problem in the easier case of pushdown systems without ε-transitions.

In the Submodular Facility Location problem (SFL) we are given a collection of $n$ clients and $m$ facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility $f$ to which we assign the subset of clients $S^f$, one has to pay the opening cost $g(S^f)$, where $g(\cdot)$ is a monotone submodular function with $g(\emptyset)=0$. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA'06] gave the current-best $O(\log n)$ approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an $O(\log\log n)$ approximation. Our approach is rather flexible and can be easily extended to generalizations and variants of SFL. In more detail, we achieve the same approximation factor for the practically relevant generalizations of SFL where the opening cost of each facility $f$ is of the form $p_f+g(S^f)$ or $w_f\cdot g(S^f)$, where $p_f,w_f\geq 0$ are input values.

Evidence-based elections aim to produce trustworthy and compelling evidence of the correctness of election outcomes, enabling the detection of problems with high probability. They require a well-curated voter-verified paper trail, compliance audits, and a rigorous tabulation audit of the election outcome, known as a risk-limiting audit (RLA). We focus on ballot polling RLAs which can require that a very large sample of ballots be drawn. The main ballot polling RLA in use today, BRAVO (based on Wald’s Sequential Probability Ratio Test), is designed for use when single ballots are drawn at random and a decision regarding whether to stop the audit or draw another ballot is taken after each ballot draw. We show that BRAVO results in significant inefficiency when directly applied to real round-by-round audits.

Dimension is an important measure of complexity for posets, which has a natural motivation from computer science: An $n$-element poset of dimension $d$ can be stored in computer memory using only $\mathcal{O}(d n)$ space, which for small $d$ is much more efficient than storing an $n\times n$ comparability matrix. The canonical poset of dimension $k$ is the so-called standard example $S_k$. Every poset which contains $S_k$ has dimension at least $k$, but there exist posets which do not contain $S_k$ for any $k\ge 2$ and have arbitrarily large dimension. By analogy to $\chi$-bounded classes of graphs, we say that a class of posets is $\dim$-bounded if the only obstruction to small dimension is containing a large standard example, i.e. the dimension of any poset $P$ in the class is bounded in terms of the size of a largest $k$ such that $P$ contains a copy of $S_k$. We show that the class of planar posets is linearly dim-bounded: planar posets which do not contain $S_k$ have dimension $\mathcal{O}(k)$. One consequence of our proof is that given a planar diagram of a poset we can efficiently $\mathcal{O}(1)$-approximate its dimension. This stands in contrast with the fact that for general posets it is NP-hard to $n^{1-\epsilon}$-approximate dimension for any $\epsilon > 0$.

This is joint work with Jędrzej Hodor, Piotr Micek and William T. Trotter.

We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate an axiom (Extended Justified Representation, EJR) that guarantees proportional representation to groups of voters with common interests. We propose a simple and attractive voting rule called the Method of Equal Shares that satisfies this axiom for arbitrary costs and approval utilities, and that satisfies the axiom up to one project for arbitrary additive valuations. This method can be computed in polynomial time. In contrast, we show that the standard method for achieving proportionality in committee elections, Proportional Approval Voting (PAV), cannot be extended to work with arbitrary costs. Finally, we introduce a strengthened axiom (Full Justified Representation, FJR) and show that it is also satisfiable, though by a computationally more expensive and less natural voting rule.

Workflow nets are a popular variant of Petri nets that allow for algorithmic formal analysis of business processes. The central decision problems concerning workflow nets deal with soundness, where the initial and final configurations are specified. Intuitively, soundness states that from every reachable configuration one can reach the final configuration. We settle the widely open complexity of the three main variants of soundness: classical, structural and generalised soundness. The first two are EXPSPACE-complete, and, surprisingly, the latter is PSPACE-complete, thus computationally simpler.

The talk is based on joint work with Michael Blondin and Philip Offtermatt.

We study the complexity of computing the Shapley value in games with externalities. We focus on two representations based on marginal contribution nets (embedded MC-nets and weighted MC-nets) and five extensions of the Shapley value to games with externalities. Our results show that while weighted MC-nets are more concise than embedded MC-nets, they have slightly worse computational properties when it comes to computing the Shapley value: two out of five extensions can be computed in polynomial time for embedded MC-nets and only one for weighted MC-nets.

Circular-arc graphs, defined as the intersection graphs of arcs of a fixed circle, are one of the simplest classes of intersection graphs, whose models do not satisfy the Helly property in general (i.e. there are circular-arc graphs in which some cliques can be represented by arcs whose common intersection is empty). In particular, some cliques of a circular-arc graph G may satisfy the Helly property in some but not all circular-arc models of G. In the talk we will consider the computational problem of searching for a model of a circular-arc graph G in which some cliques of G (also given in the input) are required to satisfy the Helly property. We show that such a problem is NP-complete and, parameterized by the number of input cliques, admits an FPT-algorithm and a polynomial kernel. We also show that some more restricted variants of this problem admit poly-time solutions. Finally, we will describe the relation of the above problems with the recognition problems of so-called H-graphs (for a fixed connected graph H, the class of H-graphs contains all intersection graphs of connected subgraphs of some subdivision of H). In particular, we will discuss the recent progress towards establishing the border between the NP-hard and P cases of H-graphs recognition.

The talk includes joint work with D. Ağaoğlu, O. Cagrici, G. Gutowski, T. Hartmann, P. Hliněný, J. Kratochvíl, T. Krawczyk, and P. Zeman.

Joint work with H. Zięba, R. Janczewski, P. Obszarski.

We consider the fundamental problems of broadcasting, gossiping and gathering in synchronous radio networks. Nodes are given labels which are binary strings. Each node knows its own label and can use it when executing the algorithm. Our goal is to construct short labeling schemes for the above communication problems in arbitrary radio networks, and to design efficient deterministic algorithms for each of these tasks, using these short schemes.We first improve the time of broadcast: we achieve time $O(D+\log^2 n)$ -- which is the optimal broadcasting time in radio networks of known topology -- using labels with only $O(1)$ bits. It shows that chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. Next, we present an algorithm for the k-gathering problem running in time $O(D + \min(k, \Delta\log n)$ with labels of length $O(\min(\log k, \log \Delta))$ -- matching the lower bound on the length of the labels for this problem.Combining these two algorithms we get an algorithm for the gossiping problem in time $O(D + \Delta\log n + \log^2 n)$ (same as the best known gossiping time in radio networks of known topology) using labels of length $O(\log \Delta)$.Our solutions for all three considered communication problems use labels of asymptotically optimal length, and distributed algorithms using those labels work in the best known time, even when compared to algorithms for centralized radio networks. In the case of broadcasting and k-gathering, the time of our algorithms is provably optimal.We consider the fundamental problems of broadcasting, gossiping and gathering in synchronous radio networks. Nodes are given labels which are binary strings. Each node knows its own label and can use it when executing the algorithm. Our goal is to construct short labeling schemes for the above communication problems in arbitrary radio networks, and to design efficient deterministic algorithms for each of these tasks, using these short schemes.We first improve the time of broadcast: we achieve time $O(D+\log^2 n)$ -- which is the optimal broadcasting time in radio networks of known topology -- using labels with only $O(1)$ bits. It shows that chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. Next, we present an algorithm for the k-gathering problem running in time $O(D + \min(k, \Delta\log n)$ with labels of length $O(\min(\log k, \log \Delta))$ -- matching the lower bound on the length of the labels for this problem.Combining these two algorithms we get an algorithm for the gossiping problem in time $O(D + \Delta\log n + \log^2 n)$ (same as the best known gossiping time in radio networks of known topology) using labels of length $O(\log \Delta)$.Our solutions for all three considered communication problems use labels of asymptotically optimal length, and distributed algorithms using those labels work in the best known time, even when compared to algorithms for centralized radio networks. In the case of broadcasting and k-gathering, the time of our algorithms is provably optimal.

We are going to show a submodularity based approach for pricing ride-hailing fares which gives (1-1/e) guarantee of approximation, beating the 1/3-approximation of Hikima et al. (AAAI 2021) who used min-cost flow methods.

In the classical global minimum cut problem, the input is an undirected graph G=(V,E) with a non-negative weight associated with every edge, and the goal is to find a non-trivial partition of its vertices into S and V\S that minimises the total weight of all edges with one endpoint in S and the other in V\S. The first question is to design an efficient algorithm for sparse graphs, that is, with the complexity depending primarily on the number of edges m. Karger designed a randomised O(m\log^3n) time algorithm for this problem. I will describe his framework, and then sketch a faster O(m\log^2n) time algorithm, and an even faster algorithm for unweighted graphs. Next, I will describe the cut query model, in which the algorithm is only allowed to access the graph by issuing cut queries. I will describe a new technique dubbed "star contraction" that allows computing the global minimum cut for unweighted *simple* graphs in this model with only O(n) such queries. Previously, such an upper bound was not known even for the simpler problem of checking if the graph is connected.

For a bipartite graph $G$ we consider the problem of finding a maximum size/weight square-free $2$-matching and its generalization - the problem of finding a maximum size/weight K{t,t}-free $t$-matching, where $t$ is an integer greater than two and K{t,t} denotes a bipartite clique with $t$ vertices on each of the two sides. Since the weighted versions of these problems are NP-hard in general, we assume that the weights are vertex-induced on any subgraph isomorphic to K{t,t}. We present simple combinatorial algorithms for these problems. Our algorithms are significantly simpler and faster than those previously known. We dispense with the need to shrink squares and, more generally subgraphs isomorphic to K{t,t}, the operation which occurred in all previous algorithms for such $t$-matchings and instead use so-called half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints.

The talk is based on a paper accepted to ESA 2021 ( Restricted t-Matchings via Half-Edges ), co-authored by Katarzyna Paluch.

A "map of elections" is a collection of election instances, together with some measure of similarity between each pair of them. The elections are represented as points in a 2D Euclidean space in such a way that the Euclidean distances between the points correspond---as best as possible---to the similarity between their elections. Naturally, maps of elections depend both on the sets of elections that they include and on the measures of similarity used to prepare them (and on the embeddings in the 2D space, which can be more or less accurate). In this talk I will present the main idea of the maps of elections, discuss several distances and their properties (both algorithmic and others), and show that maps of elections are very useful tools for visualizing experimental results. In particular, maps allows to show results on large numbers of election instances in a way that shows all individual results jointly, without relying on aggregated measures (such as averages or variations).

Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce two time-dependent multistage models based on simple scoring-based voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, where each voter is allowed to support at most one candidate. Our task is to find a small committee of high score for each stage. In the conservative model, we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be “easier” than being conservative. Employing the concept of polynomial kernels, we also show some effective preprocessing procedures yielding provable guarantees with respect to shrinking the instance size. Finally, many of our algorithmic results naturally extend to a broader collection of scoring-based voting rules, where each voter approves an arbitrary number of candidates or where each candidate receives some score.

We investigate ties in multiwinner approval voting both theoretically and experimentally. Specifically, we study the complexity of deciding if there is a tie in a given approval-based multiwinner election, as well as the complexity of counting tied winning committees. We consider a large family of Thiele rules (more precisely, 1-concave Thiele rules), their greedy variants, Satisfaction Approval Voting (SAV) rule, and Phragmen sequential rule. Among 1-concave Thiele rules, we put attention to three commonly known rules: Approval Voting (AV) rule, Chamberlin-Courant (CC) rule, and Proportional Approval Voting (PAV) rule. We show that our problems (detecting ties and counting winning committees) are polynomial-time solvable for AV and SAV whereas they are computationally hard for the remaining rules. For computationally hard problems, we also study the parameterization by the committee size. For the greedy rules and Phragmen we find an FPT algorithm for discovering ties (parameterized by the committee size), and (#)W-hardness for the remaining cases. We also conduct experiments to see how frequently ties occur for different rules and models. We concentrate on three approval election generation models: resampling model, disjoint model, and euclidean model. We show experimentally that in elections of moderate size ties are quite frequent and that we need to find a way of addressing them.

We employ the technique of Schnyder labellings to derive a new simplified proof of the fact that the Alon-Tarsi number of a planar graph is at most 5. We discuss how this seemingly new approach is related to previous proofs that were based on the famous Thomassen's argument for the choice number.

This is joint work with Jakub Kozik.

We study discrete two player all-pay auction with complete information. We provide full characterization of mixed strategy Nash equilibria and show that they constitute a subset of Nash equilibria of discrete General Lotto game. We show that equilibria are not unique in general but they are interchangeable. We also show that equilibrium payoffs are unique, unless valuation of at least one of the players is an even integer number. If equilibrium payoffs are not unique, continuum of equilibrium payoffs are possible. We compare equilibrium characterization and equilibrium payoffs with the continuous variant of all-pay auctions.

During the talk I will present our ongoing work with Damian Niwiński and Paweł Parys on computing measures of regular languages. Our approach (following earlier results with Marcin Przybyłko) is to reduce the problem to evaluation of certain fixpoint expression in a specific ordered set (called Probabilistic Powerdomain). My goal is to present the overall technique.

We will survey the results on the collapses of the bounded width hierarchy over both finite and infinite homogeneous structures.