### Browsing by Author "Dahal, Sameep"

Now showing 1 - 4 of 4

###### Results Per Page

###### Sort Options

Item Brief Announcement : Distributed Derandomization Revisited(Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023-10) Dahal, Sameep; d'Amore, Francesco; Lievonen, Henrik; Picavet, Timothe; Suomela, Jukka; Department of Computer Science; Computer Science Professors; Oshman, RotemOne of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions - it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.Item Distributed Half-Integral Matching and Beyond(Springer, 2023) Dahal, Sameep; Suomela, Jukka; Department of Computer Science; Computer Science Professors; Rajsbaum, Sergio; Balliu, Alkida; Olivetti, Dennis; Daymude, Joshua J.By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω(log∗n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0,12,1}. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ=2d, and any distributed graph algorithm with round complexity T(Δ) that only depends on Δ and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.Item Distributed half-integral matching and beyond(Elsevier Science B.V., 2024-01-08) Dahal, Sameep; Suomela, Jukka; Department of Computer Science; Computer Science Professors; Department of Computer ScienceBy prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω(log⁎n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from [Formula presented]. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ=2d, and any distributed graph algorithm with round complexity T(Δ) that only depends on Δ and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.Item Understanding the Distributed Complexity of Infinite Problems(2023-08-21) Dahal, Sameep; Suomela, Jukka; Perustieteiden korkeakoulu; Suomela, JukkaDistributed computing refers to the method where multiple computers on a communication network work together to solve some common problem. The underlying network can be viewed as a graph $G=(V,E)$ where the computers act as vertices, and the communication links between the computers act as edges. In order to solve a specific problem, all the computers, in parallel, run their own version of the algorithm. An example of a problem studied in distributed computing is the problem of finding a maximal matching of the underlying network. In this problem, we need to pick a set of edges $M$ which satisfies two properties: (1)\ no two edges in $M$ can share a vertex, and (2)\ no more edges can be added to $M$ so that property (1) is still maintained. The problem can also be viewed as computing a function $f\colon E \rightarrow \{0,1\}$ such that for a given edge $e$, $f(e) = 1$ if and only if $e \in M$. In this thesis, I am interested in understanding infinite problems in the distributed setting. An infinite problem refers to a problem whose solution space is infinite. An example of such a problem is the problem of finding a maximal fractional matching. It is the fractional relaxation of the maximal matching problem, and allows for the function $f$ to take any fractional value from $0$ and $1$. While finite problems (problems with finite solution space) have been studied extensively in the distributed setting, relatively little work has been done to formalize the notion of infinite problems. This thesis provides a definition for infinite problems, in a way that it can be represented using finite description. After defining infinite problems, one question arises naturally: can a given infinite problem be solved without any communication (i.e.,\ in $0$ rounds)? This problem is well understood for finite problems; there exists an algorithm that decides whether a given finite problem can be solved using $0$ rounds or not. In this thesis, I give an algorithm that answers the same for infinite problems. Moreover, I also investigate automatic tools to derive lower bounds for infinite problems. In particular, I focus on round elimination for the maximal fractional matching problem. Round elimination is a technique that has been used successfully for obtaining tight lower bounds for finite problems such as maximal matching and sinkless orientation. However, the same technique has not been used for infinite problems. I study the application of round elimination for the fractional variant of maximal matching and develop techniques that help to analyze the result of round elimination on maximal fractional matching.