### Browsing by Author "Hirvonen, Juho"

Now showing 1 - 20 of 21

###### Results Per Page

###### Sort Options

Item Adversiaalinen haku täydellisen tiedon peleissä(2023-12-15) Pollari, Visa; Hirvonen, Juho; Perustieteiden korkeakoulu; Kannala, JuhoItem Brief Announcement: Classification of Distributed Binary Labeling Problems(2020-07-31) Balliu, Alkida; Brandt, Sebastian; Efron, Yuval; Hirvonen, Juho; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Computer Science - Algorithms and Theoretical Computer Science (TCS); ETH Zurich; Technion - Israel Institute of Technology; University of FreiburgWe present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.Item Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020) Foerster, Klaus Tycho; Hirvonen, Juho; Pignolet, Yvonne-Anne; Schmid, Stefan; Tredan, Gilles; Department of Computer Science; Attiya, Hagit; Professorship Suomela J.; University of Vienna; DFINITY; Centre National de la Recherche Scientifique (CNRS)In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.Item Classification of Distributed Binary Labeling Problems(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020) Balliu, Alkida; Sebastian, Brandt; Efron, Yuval; Hirvonen, Juho; Maus, Yannic; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Attiya, Hagit; Professorship Suomela J.; Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich; Technion - Israel Institute of Technology; Albert-Ludwigs-Universität FreiburgWe present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity Θ(log^* n), and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.Item Geometriset vikasietoiset virittäjät(2023-04-17) Hakala, Nuutti; Hirvonen, Juho; Perustieteiden korkeakoulu; Hyvönen, EeroItem Graafisten pelien analysoiminen soveltaen hajautetun laskennan teoriaa(2022-02-19) Alaharju, Henri; Hirvonen, Juho; Perustieteiden korkeakoulu; Hyvönen, EeroItem A Hierarchy of Local Decision(Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Université Sorbonne Paris Cité; Department of Computer Science; Ioannis Chatzigiannakis Michael Mitzenmacher, Yuval Rabani; Sangiorgi, DavideWe extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with O(log n)-bit certificates in n-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires(log2 n)-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires (n2) bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with O(log n)- bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs.Item A hierarchy of local decision(ELSEVIER SCIENCE BV, 2021-02-08) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Department of Computer Science; Professorship Suomela J.; Universidad de Chile; Institut de Recherche en Informatique FondamentaleWe extend the notion of distributed decision in the framework of distributed network computing, inspired by both the polynomial hierarchy for Turing machines and recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree (MST) can be certified with O(logn)-bit certificates in n-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires Ω(log2n)-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires Ω(n2) bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover that certifies nontrivial automorphism with O(logn)-bit certificates. These results are achieved by defining and analyzing a local hierarchy of decision which generalizes the classical notions of proof-labeling schemes and locally checkable proofs.Item Improved distributed degree splitting and edge coloring(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2017) Ghaffari, Mohsen; Hirvonen, Juho; Kuhn, Fabian; Maus, Yannic; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Professorship Suomela J.; Swiss Federal Institute of Technology Zurich; University of Freiburg; Institut de Recherche en Informatique FondamentaleThe degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.Item Improved distributed Δ -coloring(Springer Verlag, 2021-08) Ghaffari, Mohsen; Hirvonen, Juho; Kuhn, Fabian; Maus, Yannic; Department of Computer Science; Professorship Suomela J.; Swiss Federal Institute of Technology Zurich; Albert-Ludwigs-Universität Freiburg; Technion - Israel Institute of TechnologyWe present a randomized distributed algorithm that computes a Δ -coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(logΔ)+2O(loglogn) rounds, as well as a randomized algorithm that computes a Δ -coloring in O((log log n) 2) rounds when Δ ∈ [3 , O(1)]. Both these algorithms improve on an O(log 3n/ log Δ) -round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Ω (log log n) round lower bound of Brandt et al. (STOC’16).Item Julkisen avaimen salauksen algoritmit(2023-04-17) Kääriäinen, Aleksi; Hirvonen, Juho; Perustieteiden korkeakoulu; Hyvönen, EeroItem Large Cuts with Local Algorithms on Triangle-Free Graphs(2017-10-20) Hirvonen, Juho; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.; Aalborg University; Institut de Recherche en Informatique Fondamentale; University of HelsinkiLet G be a d-regular triangle-free graph with in edges. We present an algorithm which finds a cut in G with at least (1/2 + 0.28125/root d)rn edges in expectation, improving upon Shearer's classic result. In particular, this implies that any d-regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of G. Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient randomised distributed (local) algorithm: each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using computational techniques. We show that for any fixed d, there exists a weighted neighbourhood graph N-d such that there is a one-to-one correspondence between heavy cuts of N-d and randomised local algorithms that find large cuts in any d-regular input graph. This turns out to be a useful tool for analysing the existence of cuts in d-regular graphs: we can compute the optimal cut of N-d to attain a lower bound on the maximum cut size of any d-regular triangle-free graph.Item Local Mending(Springer, 2022) Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya; Olivetti, Dennis; Rybicki, Joel; Suomela, Jukka; Gran Sasso Science Institute; Department of Computer Science; Institute of Science and Technology Austria; Computer Science Professors; Parter, MeravIn this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.Item Local Verification of Global Proofs(Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018-10-01) Feuilloley, Laurent; Hirvonen, Juho; Department of Computer Science; Schmid, Ulrich; Hirvonen, Juho; Professorship Suomela J.; Paris Diderot UniversityIn this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof for the correctness of the state of the system, and the nodes need to verify this proof by looking at only their local neighborhood in the system. Previous works have studied the model where each node is given its own, possibly unique, part of the proof as input. The cost of a proof is the maximum size of an individual label. We compare this model to a model where each node has access to the same global proof, and the cost is the size of this global proof. It is easy to see that a global proof can always include all of the local proofs, and every local proof can be a copy of the global proof. We show that there exists properties that exhibit these relative proof sizes, and also properties that are somewhere in between. In addition, we introduce a new lower bound technique and use it to prove a tight lower bound on the complexity of reversing distributed decision and establish a link between communication complexity and distributed proof complexity.Item Lower bounds in distributed computing(Aalto University, 2016) Hirvonen, Juho; Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland; Tietotekniikan laitos; Department of Computer Science; Distributed Algorithms; Perustieteiden korkeakoulu; School of Science; Suomela, Jukka, Prof., Aalto University, Department of Computer Science, FinlandIn this thesis I study the complexity theory of distributed computing in synchronous message passing models. The focus is on highly local problems, that is, problems in which very little communication is required. In this setting the underlying communication network is also the input graph. The distributed system must collectively compute a solution to a problem related to the structure of this network, with each computer producing its own part of the output. We study the LOCAL model, one of the standard models in distributed computing. It abstracts away faults, congestion, computational requirements, memory requirements, and many other challenges in distributed computing. We study this model to understand the locality aspect of distributed computing: How far does information have to propagate in distributed problem solving? How many communication rounds is required? Many interesting problems, such as finding a spanning tree in the communication network, are inherently global. We are interested in the other extreme: problems that can be solved in time that is weakly dependent or completely independent of the size of the communication network. Typical problems include classical symmetry breaking tasks such as colouring or maximal independent set. Typically the time complexity of such problems depends on two parameters: the size and the maximum degree of the input graph. The connection with the first parameter is well understood with tight upper and lower bounds. The connection with the maximum degree is much less well understood, with an exponential gap between the upper and lower bounds. We develop a new lower bound technique to give the first lower bound for a natural graph problem that is linear in the maximum degree. In addition we study the power of unique in several contexts. We show that while usually unique identifiers are unhelpful for constant-time algorithms, there are certain special cases in which they do help. In the context of local decision, where the task is essentially to verify a given solution instead of constructing a new one, we characterize the minimal information that is sufficient to replace unique identifiers. Finally, we also study the power of nondeterminism in local decision. We develop a local hierarchy in a manner analogous to the polynomial hierarchy in centralized computing, and study the structure of this hierarchy. The focus of this thesis is on structural results, especially lower bounds. The lower bounds as a function of the maximum degree of the graph employ a completely novel proof technique based on graph symmetries.Item New classes of distributed time complexity(2018-06-20) Balliu, Alkida; Hirvonen, Juho; Korhonen, Janne H.; Lempiäinen, Tuomo; Olivetti, Dennis; Suomela, Jukka; Department of Computer Science; Professorship Suomela J.A number of recent papers – e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) – have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem Π in which a solution can be verified by checking all radius-O(1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius-T neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Θ(1), Θ(log∗ n), Θ(log n), Θ(n1/k), and Θ(n). It is also known that there are two gaps: one between ω(1) and o(log log∗ n), and another between ω(log∗ n) and o(log n). It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple – indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Θ(logα n) for any α ≥ 1, 2Θ(log^α n) for any α ≤ 1, and Θ(nα) for any α < 1/2 in the high end of the complexity spectrum, and Θ(logα log∗ n) for any α ≥ 1, 2Θ(log^α log^∗ n) for any α ≤ 1, and Θ((log∗ n)α) for any α ≤ 1 in the low end of the complexity spectrum; here α is a positive rational number.Item On the Convergence Time in Graphical Games : A Locality-Sensitive Approach(2024-01) Hirvonen, Juho; Schmid, Laura; Chatterjee, Krishnendu; Schmid, Stefan; Department of Computer Science; Bessani, Alysson; Defago, Xavier; Nakamura, Junya; Wada, Koichi; Yamauchi, Yukiko; Helsinki Institute for Information Technology (HIIT); Professorship Suomela J.; Korea Advanced Institute of Science and Technology; Institute of Science and Technology Austria; Technical University of BerlinGraphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of “natural” local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of “time-constrained” inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.Item Ordered cover-free families in graph coloring(2021-08-23) Karkinen, Antti; Hirvonen, Juho; Perustieteiden korkeakoulu; Suomela, JukkaDistributed computing is a subfield of theoretical computer science that studies distributed systems, where multiple components interact with one another in order to achieve some common goal. Distributed algorithms are used in many areas of distributed computing, such as telecommunications, scientific computing, and distributed information processing. One of the most fundamental graph problems is vertex coloring. In the extensively studied LOCAL model, Linial showed (1992) that cover-free families can be used to reduce the number of colors fast. In this thesis, I will give the reader a brief introduction to distributed algorithms, graph coloring, and related subjects. I will do a short survey on what is already known about cover-free families and define more constricted ordered cover-free families. Next, I show how these ordered cover-free families can be used to create a single-round color reduction algorithm. In this work, highly optimized SAT solvers were used to find cover-free families. SAT solvers are designed to solve Boolean satisfiability problems and in this thesis, I show one way to encode cover-free families as Boolean satisfiability problems. Utilizing the PySAT toolkit, I created a Python program that was run on a virtual machine service for a few months. This dataset, containing both unordered and ordered cover-free families, was used to compare the runtimes of single-round color reduction algorithms. In paths and circles, the algorithm based on ordered cover-free families is slower than already known best color reduction algorithms, but it is still faster than earlier algorithms using unordered cover-free families.Item Redundancy in Distributed Proofs(Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018-10-01) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor; Department of Computer Science; Schmid, Ulrich; Hirvonen, Juho; Professorship Suomela J.; Institut de Recherche en Informatique Fondamentale; Tel Aviv UniversityDistributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data structures distributed over the nodes (e.g. a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.Item Redundancy in distributed proofs(Springer Verlag, 2020-10-07) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor; Department of Computer Science; Professorship Suomela J.; Universidad de Chile; Institut de Recherche en Informatique Fondamentale; University of Vienna; Weizmann Institute of ScienceDistributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called a verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.