Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Latypov, Rustam"'
We give the first parallel algorithm with optimal $\tilde{O}(m)$ work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edges. In graphs without negative edges, Dijkstra's algorithm solves the
Externí odkaz:
http://arxiv.org/abs/2410.20959
Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures the central challenges in data center computations. Chan
Externí odkaz:
http://arxiv.org/abs/2402.13755
We 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 algor
Externí odkaz:
http://arxiv.org/abs/2308.00355
Autor:
Gupta, Chetan, Latypov, Rustam, Maus, Yannic, Pai, Shreyas, Särkkä, Simo, Studený, Jan, Suomela, Jukka, Uitto, Jara, Vahidi, Hossein
We 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^\delta)$ words of local memory per machine, for any given consta
Externí odkaz:
http://arxiv.org/abs/2305.03693
We 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)$ roun
Externí odkaz:
http://arxiv.org/abs/2302.04033
We 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 set
Externí odkaz:
http://arxiv.org/abs/2211.03530
Autor:
Balliu, Alkida, Brandt, Sebastian, Fischer, Manuela, Latypov, Rustam, Maus, Yannic, Olivetti, Dennis, Uitto, Jara
Locally 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 se
Externí odkaz:
http://arxiv.org/abs/2208.09453
In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method that solves most locally checkable labeling (LCL) problems exponentially
Externí odkaz:
http://arxiv.org/abs/2112.09479
Autor:
Latypov, Rustam, Uitto, Jara
We present $O(\log^2 \log n)$ time 3-coloring, maximal independent set and maximal matching algorithms for trees in the Massively Parallel Computation (MPC) model. Our algorithms are deterministic, apply to arbitrary-degree trees and work in the low-
Externí odkaz:
http://arxiv.org/abs/2105.13980
Autor:
Latypov, Rustam, Stolov, Evgeni
There are a few reasons for the recent increased interest in the study of local features of speech files. It is stated that many essential features of the speaker language used can appear in the form of the speech signal. The traditional instruments
Externí odkaz:
http://arxiv.org/abs/2006.03388