### Browsing by Author "Pai, Shreyas"

Now showing 1 - 5 of 5

###### Results Per Page

###### Sort Options

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 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 Risk-aware temporal cascade reconstruction to detect asymptomatic cases(SPRINGER, 2022-12) Jang, Hankyu; Pai, Shreyas; Adhikari, Bijaya; Pemmaraju, Sriram V.; University of Iowa; Department of Computer ScienceThis paper studies the problem of detecting asymptomatic cases in a temporal contact network in which multiple outbreaks have occurred. We show that the key to detecting asymptomatic cases well is taking into account both individual risk and the likelihood of disease-flow along edges. We consider both aspects by formulating the asymptomatic case detection problem as a directed prize-collecting Steiner tree (Directed PCST) problem. We present an approximation-preserving reduction from this problem to the directed Steiner tree problem and obtain scalable algorithms for the Directed PCST problem on instances with more than 1.5M edges obtained from both synthetic and fine-grained hospital data. On synthetic data, we demonstrate that our detection methods significantly outperform various baselines (with a gain of 3.6 ×). We apply our method to the infectious disease prediction task by using an additional feature set that captures exposure to detected asymptomatic cases and show that our method outperforms all baselines. We further use our method to detect infection sources (“patient zero”) of outbreaks that outperform baselines. We also demonstrate that the solutions returned by our approach are clinically meaningful by presenting case studies.Item Sinkless Orientation Made Simple(2023-01-12) Balliu, Alkida; Korhonen, Janne H.; Kühn, Fabian; Lievonen, Henrik; Olivetti, Dennis; Pai, Shreyas; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Studený, Jan; Suomela, Jukka; Uitto, Jara; Gran Sasso Science Institute; IST Austria; University of Freiburg; Department of Computer Science; University of Vienna; Aalborg University; Computer Science ProfessorsThe sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.Item Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem(2023-10) Cambus, Mélanie; Kuhn, Fabian; Pai, Shreyas; Uitto, Jara; Department of Computer Science; Oshman, Rotem; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); University of FreiburgIn this work, we present a constant-round algorithm for the 2-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the O(log log log n)-round algorithm by [HPS, DISC'14] and the O(log log ∆)-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an O(1)-pass algorithm. Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.