### Browsing by Author "Latypov, Rustam"

Now showing 1 - 9 of 9

###### Results Per Page

###### Sort Options

Item Adaptive Massively Parallel Connectivity in Optimal Space(2023-06-17) Latypov, Rustam; Łacki, Jakub; Maus, Yannic; Uitto, Jara; Department of Computer Science; Google Research; Graz University of Technology; Computer Science ProfessorsWe study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.Item Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2021) Brandt, Sebastian; Latypov, Rustam; Uitto, Jara; ETH Zurich; Professorship Uitto J.; Computer Science Professors; Department of Computer Science; Gilbert, SethWe establish scalable Massively Parallel Computation (MPC) algorithms for a family of fundamental graph problems on trees. We give a general method that, for a wide range of LCL problems, turns their message passing counterparts into exponentially faster algorithms in the sublinear MPC model. In particular, we show that any LCL on trees that has a deterministic complexity of O(n) in the LOCAL model can be sped up to O(log n) (high-complexity regime) in the sublinear MPC model and similarly n^{o(1)} to O(log log n) (intermediate-complexity regime). We emphasize, that we work on bounded degree trees and all of our algorithms work in the sublinear MPC model, where local memory is O(n^δ) for δ < 1 and global memory is O(m). For the high-complexity regime, one key ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL on trees with a sublinear MPC algorithm with complexity O(log n). For the intermediate-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical algorithm for solving LCL problems on trees in the LOCAL model. For the special case of 3-coloring trees, which is a natural LCL problem, we provide a conditional Ω(log log n) lower bound, implying that solving LCL problems on trees with deterministic LOCAL complexity n^{o(1)} requires Θ(log log n) deterministic time in the sublinear MPC model when using a natural family of component-stable algorithms.Item Coloring Sparse Graphs with 3 Colors in the Massively Parallel Computation (MPC) Model Using Strongly Sublinear Memory(2021-01-26) Latypov, Rustam; Uitto, Jara; Perustieteiden korkeakoulu; Uitto, JaraThe question of what problems can be solved, and how efficiently, has always been at the core of theoretical computer science. One such fundamental problem is graph coloring; it is well researched and has numerous applications in areas of computer science such as scheduling and pattern matching. The challenges faced when designing graph coloring algorithms are dictated by the underlying graph family, the number of colors allowed, and the model of computation. In this work we consider the graph family of trees and the distributed Massively Parallel Computation (MPC) model, introduced by Karloff et al. \cite{karloff}. Our contribution to the field of distributed computing is a deterministic strongly sublinear MPC algorithm for 3-coloring unbounded degree trees with $n$ nodes in $O(\log \log n)$ time. To the best of our knowledge, this is the current state-of-the-art algorithm, improving on the work of Ghaffari et al. \cite{ghaffari}. It is loosely based on two previous works by Brandt et al. \cite{sparce,sirocco}. Before computing a 3-coloring, our algorithm partitions the input tree into disjoint node sets $H_1,H_2,\dots,H_l$, in $O(\log \log n)$ time. For each node $v \in H_i$, it holds that $v$ has at most two neighbors in the set $\bigcup_{j=i}^l H_j$. We consider this partitioning in and of itself an important contribution, since it has the potential of being a useful subroutine in future algorithms. For example, a similar technique was used by Chang et al. \cite{chang} in their seminal paper to establish an important time hierarchy theorem for the distributed LOCAL model on trees.Item Conditionally Optimal Parallel Coloring of Forests(2023-10) Grunau, Christoph; Latypov, Rustam; Maus, Yannic; Pai, Shreyas; Uitto, Jara; Department of Computer Science; Oshman, Rotem; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich; Department of Computer Science; Graz University of TechnologyWe show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous algorithm requires 4 colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an O(log log n)-round algorithm to compute a partition of the forest into O(log n) ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.Item Distributed Drawing of Planar Graphs in the CONGEST model(2022-07-29) Sederholm, Hannes; Latypov, Rustam; Perustieteiden korkeakoulu; Uitto, JaraThe concept of planarity has been widely studied in many contexts. However, in the distributed setting and specifically in the CONGEST model, relatively little work has been done in the area. Especially, the problem of drawing planar graphs has not been solved previously in CONGEST. In this thesis the problem is studied by inspecting existing non-distributed algorithms. As a result a novel CONGEST algorithm solving this problem is presented. The algorithm utilizes an existing distributed algorithm to obtain a combinatorial embedding of a graph. Given the running time of obtaining an embedding the running time of the algorithm is negligible, and thus analysis of the performance of the algorithm focuses on the quality of the drawings. The quality of the drawings are evaluated with examples created by programmatically simulating the execution of the algorithm.Item Exponential Speedup over Locality in MPC with Optimal Memory(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2022-10-17) Balliu, Alkida; Sebastian, Brandt; Fischer, Manuela; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Gran Sasso Science Institute; CISPA Helmholtz Center for Information Security; ETH Zurich; Professorship Uitto J.; Graz University of Technology; Computer Science Professors; Department of Computer Science; Scheideler, ChristianLocally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.Item Fast Dynamic Programming in Trees in the MPC Model(2023-06-17) Gupta, Chetan; Latypov, Rustam; Maus, Yannic; Pai, Shreyas; Särkkä, Simo; Studený, Jan; Suomela, Jukka; Uitto, Jara; Vahidi, Hossein; Department of Computer Science; Department of Electrical Engineering and Automation; Professorship Uitto J.; Helsinki Institute for Information Technology (HIIT); Sensor Informatics and Medical Technology; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; Department of Computer Science; Graz University of TechnologyWe present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ< 1. Here D is the diameter of the tree and n is the number of nodes - -we emphasize that our running time is independent of n. Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree - -this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of O(log D) rounds is also known to be necessary, assuming the widely-believed 2-cycle conjecture. Our algorithm strictly improves on two prior algorithms: Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in O(log n) rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in O(log D) rounds, while our algorithm can be applied to a much broader family of problems.Item Inverse problem for resistor networks(2018-09-18) Latypov, Rustam; Hannukainen, Antti; Perustieteiden korkeakoulu; Hannukainen, AnttiItem Optimal Deterministic Massively Parallel Connectivity on Forests(2023) Balliu, Alkida; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Gran Sasso Science Institute; Professorship Uitto J.; Graz University of Technology; Computer Science Professors; Department of Computer ScienceWe show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent breakthrough result by Coy and Czumaj [STOC'22] shows that, in this setting, it is possible to deterministically identify connected components on graphs in O (log D + log log n) rounds, where D is the diameter of the graph and n the number of nodes. The authors left open a major question: is it possible to get rid of the additive log log n factor and deterministically identify connected components in a runtime that is completely independent of n? We answer the above question in the affirmative in the case of forests. We give an algorithm that identifies connected components in O(log D) deterministic rounds. The total memory required is O(n + m) words, where m is the number of edges in the input graph, which is optimal as it is only enough to store the input graph. We complement our upper bound results by showing that Ω(logD) time is necessary even for component-unstable algorithms, conditioned on the widely believed 1 vs. 2 cycles conjecture. Our techniques also yield a deterministic forest-rooting algorithm with the same runtime and memory bounds. Furthermore, we consider Locally Checkable Labeling problems (LCLs), whose solution can be verified by checking the O(1)-radius neighborhood of each node. We show that any LCL problem on forests can be solved in O (log D) rounds with a canonical deterministic algorithm, improving over the O (log n) runtime of Brandt, Latypov and Uitto [DISC'21]. We also show that there is no algorithm that solves all LCL problems on trees asymptotically faster.