### Browsing by Department "Professorship Suomela J."

Now showing 1 - 5 of 5

###### Results Per Page

###### Sort Options

Item Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens(2020-10-07) Chang, Yi-Jun; Studený, Jan; Suomela, Jukka; ETH Zurich; Department of Computer Science; Professorship Suomela J.We study the following algorithm synthesis question: given the description of a locally checkable graph problem Π for paths or cycles, determine in which instances Π is solvable, determine what is the locality of Π, and construct an asymptotically optimal distributed algorithm for solving Π (in the usual LOCAL model of distributed computing). To answer such questions, we represent Π as a nondeterministic finite automaton ℳ over a unary alphabet, and identify polynomial-time-computable properties of automaton ℳ that capture the locality and solvability of problem Π.Item Constant space and non-constant time in distributed computing(Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018-03) Lempiäinen, Tuomo; Suomela, Jukka; Professorship Suomela J.; Department of Computer ScienceWhile the relationship of time and space is an established topic in traditional centralised complexity theory, this is not the case in distributed computing. We aim to remedy this by studying the time and space complexity of algorithms in a weak message-passing model of distributed computing. While a constant number of communication rounds implies a constant number of states visited during the execution, the other direction is not clear at all. We consider several graph families and show that indeed, there exist non-trivial graph problems that are solvable by constant-space algorithms but that require a non-constant running time. This provides us with a new complexity class for distributed computing and raises interesting questions about the existence of further combinations of time and space complexity.Item Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms(2023-07-05) Akbari, Amirreza; Eslami, Navid; Lievonen, Henrik; Melnyk, Darya; Särkijärvi, Joona; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Computer Science Professors; Department of Computer Science; Etessami, Kousha; Feige, Uriel; Puppis, GabrieleIn this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary presents the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each node we get to see its radius-T neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, the SLOCAL model, which is the sequential counterpart of LOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models. In general, all four models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems extensively studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class – O(log∗ n), Θ(log n), or nΘ(1) – in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in two-dimensional grids or general bipartite graphs. We provide an online-LOCAL algorithm with locality O(log n) for the 3-coloring problem in bipartite graphs – this is a problem with locality Ω(n1/2) in the LOCAL model and Ω(n1/10) in the SLOCAL model.Item On Non-Cooperativeness in Social Distance Games(Morgan Kaufmann Publishers, Inc., 2019) Balliu, Alkida; Flammini, Michele; Melideo, Giovanna; Olivetti, Dennis; Professorship Suomela J.; University of L'Aquila; Department of Computer ScienceWe consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.Item Variation in the productivity of adjective comparison in Present-day English(2018) Säily, Tanja; González-Díaz, Victorina; Suomela, Jukka; Professorship Suomela J.; Department of Computer Science; Brezina, Vaclav; Love, Robbie; Aijmer, KarinThis chapter explores intra- and extra-linguistic variation and change in the productivity of adjective comparison in present-day spoken English (BNC1994 and BNC2014). While some intra-linguistic factors seem to have an impact on the productivity of the periphrastic comparative strategy, the overall picture is that of stability in its productivity over time and across social categories. By contrast, the inflectional strategy appears to have become significantly more productive in the recent history of British English, and some of this change is clearly influenced by extra-linguistic factors such as gender and social class. Similar sociolinguistic variation has recently been found in the productivity of derivational morphology, supporting the hypothesis of a cline between derivation and inflection rather than a sharp divide. The present work therefore has implications for the study of synthetic vs. analytic trends in English (which has often excluded derivation): in line with previous morphological research, the results provide further empirical evidence to suggest that derivation should be viewed as contributing to syntheticity alongside inflection.