The Experts below are selected from a list of 94350 Experts worldwide ranked by ideXlab platform
Jara Uitto - One of the best experts on this subject based on the ideXlab platform.
-
conditional hardness results for massively Parallel Computation from distributed lower bounds
Foundations of Computer Science, 2019Co-Authors: Mohsen Ghaffari, Fabian Kuhn, Jara UittoAbstract:We present the first conditional hardness results for massively Parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively Parallel Computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively Parallel Computation setting.
-
massively Parallel Computation of matching and mis in sparse graphs
Principles of Distributed Computing, 2019Co-Authors: Soheil Behnezhad, Richard M Karp, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, Mohammadtaghi Hajiaghayi, Jara UittoAbstract:The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale Parallel Computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model.These problems are known to admit efficient MPC algorithms if the space available per machine is near-linear in the number n of nodes. This is not only often significantly more than what we can afford, but also allows for easy if not trivial solutions for sparse graphs---which are common in real-world large-scale graphs. We are, therefore, interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, nδ for any constant 0
-
the complexity of δ 1 coloring in congested clique massively Parallel Computation and centralized local Computation
Principles of Distributed Computing, 2019Co-Authors: Yijun Chang, Manuela Fischer, Jara Uitto, Mohsen Ghaffari, Yufan ZhengAbstract:In this paper, we present new randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (Δ+1)-list-coloring, in three well-studied models of distributed, Parallel, and centralized Computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Δ + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log* Δ)-round randomized algorithms of Parter and Su [DISC'18] and O((log log Δ)⋅ log* Δ)-round randomized algorithm of Parter [ICALP'18]. Massively Parallel Computation: We present a randomized (Δ + 1)-list-coloring algorithm with round complexity O(√ log log n ) in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of O(nα) per machine, for any desirable constant α > 0, and a total memory of O (m), where m is the number of edges in the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, an O(1)-round algorithm was given very recently by Assadi et al. [SODA'19]. Centralized Local Computation: We show that (Δ + 1)-list-coloring can be solved by a randomized algorithm with query complexity Δ O(1) … O(log n), in the centralized local Computation model. The previous state of the art for (Δ+1)-list-coloring in the centralized local Computation model are based on simulation of known LOCAL algorithms. The deterministic O(√ Δ poly log Δ + log* n)-round LOCAL algorithm of Fraigniaud et al. [FOCS'16] can be implemented in the centralized local Computation model with query complexity ΔO(√ Δ poly log Δ) … O(log* n); the randomized O(log* Δ) + 2^O(√ log log n)-round LOCAL algorithm of Chang et al. [STOC'18] can be implemented in the centralized local Computation model with query complexity ΔO(log* Δ) … O(log n).
-
sparsifying distributed algorithms with ramifications in massively Parallel Computation and centralized local Computation
Symposium on Discrete Algorithms, 2019Co-Authors: Mohsen Ghaffari, Jara UittoAbstract:We introduce a method for "sparsifying" distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA).• MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic O(log n)-round Parallel (PRAM) counterparts for problems such as Maximal Independent Set (MIS), Maximal Matching, 2-Approximation of Minimum Vertex Cover, and (1 + e)-Approximation of Maximum Matching. Currently, all such MPC algorithms require memory of [MATH HERE] per machine: Czumaj et al. [STOC'18] were the first to handle [MATH HERE] memory, running in O((log log n)2) rounds, who improved on the n1+Ω(1) memory requirement of the O(1)-round algorithm of Lattanzi et al [SPAA'11]. We obtain [MATH HERE]-round MPC algorithms for all these four problems that work even when each machine has strongly sublinear memory, e.g., nα for any constant α ϵ (0, 1). Here, Δ denotes the maximum degree. These are the first sublogarithmic-time MPC algorithms for (the general case of) these problems that break the linear memory barrier.• LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity ΔO(log Δ) poly(log n), by Ghaffari [SODA'16], which improved over the ΔO(log2 Δ) poly(log n) bound of Levi et al. [Algorithmica'17]. As pointed out by Rubinfeld, obtaining a query complexity of poly(Δ log n) remains a central open question. Ghaffari's bound almost reaches a [MATH HERE] barrier common to all known MIS LCAs, which simulate a distributed algorithm by learning the full local topology, a la Parnas-Ron [TCS'07]. There is a barrier because the distributed complexity of MIS has a lower bound of [MATH HERE], by results of Kuhn, et al. [JACM'16], which means this methodology cannot go below query complexity [MATH HERE]. We break this barrier and obtain an LCA for MIS that has a query complexity ΔO(log log Δ) poly(log n).
-
sparsifying distributed algorithms with ramifications in massively Parallel Computation and centralized local Computation
arXiv: Data Structures and Algorithms, 2018Co-Authors: Mohsen Ghaffari, Jara UittoAbstract:We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). - MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic $O(\log n)$-round Parallel counterparts for problems such as MIS, Maximal Matching, 2-Approximation of Minimum Vertex Cover, and $(1+\epsilon)$-Approximation of Maximum Matching. Currently, all such MPC algorithms require $\tilde{\Omega}(n)$ memory per machine. Czumaj et al. [STOC'18] were the first to handle $\tilde{\Omega}(n)$ memory, running in $O((\log\log n)^2)$ rounds. We obtain $\tilde{O}(\sqrt{\log \Delta})$-round MPC algorithms for all these four problems that work even when each machine has memory $n^{\alpha}$ for any constant $\alpha\in (0, 1)$. Here, $\Delta$ denotes the maximum degree. These are the first sublogarithmic-time algorithms for these problems that break the linear memory barrier. - LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity $\Delta^{O(\log \Delta)} poly(\log n)$, by Ghaffari [SODA'16]. As pointed out by Rubinfeld, obtaining a query complexity of $poly(\Delta\log n)$ remains a central open question. Ghaffari's bound almost reaches a $\Delta^{\Omega\left(\frac{\log \Delta}{\log\log \Delta}\right)}$ barrier common to all known MIS LCAs, which simulate distributed algorithms by learning the local topology, a la Parnas-Ron [TCS'07]. This barrier follows from the $\Omega(\frac{\log \Delta}{\log\log \Delta})$ distributed lower bound of Kuhn, et al. [JACM'16]. We break this barrier and obtain an MIS LCA with query complexity $\Delta^{O(\log\log \Delta)} poly(\log n)$.
Satoru Miyano - One of the best experts on this subject based on the ideXlab platform.
-
sensitivity analysis of agent based simulation utilizing massively Parallel Computation and interactive data visualization
PLOS ONE, 2019Co-Authors: Atsushi Niida, Takanori Hasegawa, Satoru MiyanoAbstract:An essential step in the analysis of agent-based simulation is sensitivity analysis, which namely examines the dependency of parameter values on simulation results. Although a number of approaches have been proposed for sensitivity analysis, they still have limitations in exhaustivity and interpretability. In this study, we propose a novel methodology for sensitivity analysis of agent-based simulation, MASSIVE (Massively Parallel Agent-based Simulations and Subsequent Interactive Visualization-based Exploration). MASSIVE takes a unique paradigm, which is completely different from those of sensitivity analysis methods developed so far, By combining massively Parallel Computation and interactive data visualization, MASSIVE enables us to inspect a broad parameter space intuitively. We demonstrated the utility of MASSIVE by its application to cancer evolution simulation, which successfully identified conditions that generate heterogeneous tumors. We believe that our approach would be a de facto standard for sensitivity analysis of agent-based simulation in an era of evergrowing Computational technology. All the results form our MASSIVE analysis are available at https://www.hgc.jp/~niiyan/massive.
-
sensitivity analysis of agent based simulation utilizing massively Parallel Computation and interactive data visualization
bioRxiv, 2019Co-Authors: Atsushi Niida, Takanori Hasegawa, Satoru MiyanoAbstract:Abstract An essential step in the analysis of agent-based simulation is sensitivity analysis, which namely examines the dependency of parameter values on simulation results. Although a number of approaches have been proposed for sensitivity analysis, they still have limitations in exhaustivity and interpretability. In this study, we propose a novel methodology for sensitivity analysis of agent-based simulation, MASSIVE (Massively Parallel Agent-based Simulations and Subsequent Interactive Visualization-based Exploration). MASSIVE takes a unique paradigm, which is completely different from those of sensitivity analysis methods developed so far, By combining massively Parallel Computation and interactive data visualization, MASSIVE enables us to inspect a broad parameter space intuitively. We demonstrated the utility of MASSIVE by its application to cancer evolution simulation, which successfully identified conditions that generate heterogeneous tumors. We believe that our approach would be a de facto standard for sensitivity analysis of agent-based simulation in an era of ever-growing Computational technology. All the result form our MASSIVE analysis is available at https://www.hgc.jp/~niiyan/massive.
Arpit Mittal - One of the best experts on this subject based on the ideXlab platform.
-
large scale Parallel Computation of the phonon boltzmann transport equation
International Journal of Thermal Sciences, 2014Co-Authors: Syed Ashraf Ali, Gautham Kollu, Sandip Mazumder, P Sadayappan, Arpit MittalAbstract:Abstract Non-equilibrium heat conduction, as occurring in modern-day sub-micron semiconductor devices, can be predicted effectively using the Boltzmann Transport Equation (BTE) for phonons. In this article, strategies and algorithms for large-scale Parallel Computation of the phonon BTE are presented. An unstructured finite volume method for spatial discretization is coupled with the control angle discrete ordinates method for angular discretization. The single-time relaxation approximation is used to treat phonon–phonon scattering. Both dispersion and polarization of the phonons are accounted for. Three different Parallelization strategies are explored: (a) band-based, (b) direction-based, and (c) hybrid band/cell-based. Subsequent to validation studies in which silicon thin-film thermal conductivity was successfully predicted, transient simulations of non-equilibrium thermal transport were conducted in a three-dimensional device-like silicon structure, discretized using 604,054 tetrahedral cells. The angular space was discretized using 400 angles, and the spectral space was discretized into 40 spectral intervals (bands). This resulted in ∼9.7 × 109 unknowns, which are approximately 3 orders of magnitude larger than previously reported Computations in this area. Studies showed that direction-based and hybrid band/cell-based Parallelization strategies resulted in similar total Computational time. However, the Parallel efficiency of the hybrid band/cell-based strategy—about 88%—was found to be superior to that of the direction-based strategy, and is recommended as the preferred strategy for even larger scale Computations.
Ninghui Sun - One of the best experts on this subject based on the ideXlab platform.
-
graphine programming graph Parallel Computation of large natural graphs for multicore clusters
IEEE Transactions on Parallel and Distributed Systems, 2016Co-Authors: Jie Yan, Guangming Tan, Ninghui SunAbstract:Graph-Parallel Computation has become a crucial component in emerging applications of web search, data analytics and machine learning. In practice, most graphs derived from real-world phenomena are very large and scale-free. Unfortunately, distributed graph-Parallel Computation of these natural graphs still suffers strong scalability issues on contemporary multicore clusters. To embrace the multicore architecture in distributed graph-Parallel Computation, we propose the framework Graphine, which features (i) A Scatter-Combine Computation abstraction that is evolved from the traditional vertex-centric approach by fusing the paired scatter and gather operations, executed separately on two edge sides, into a one-sided scatter. Further coupled with active message mechanism, it potentially reduces intermediate message cost and enables fine-grained Parallelism on multicore architecture. (ii) An Agent-Graph data model, which leverages an idea similar to vertex-cut but conceptually splits the remote replica into two agent types of scatter and combiner, resulting in less communication. We implement the Graphine framework and evaluate it using several representative algorithms on six large real-world graphs and a series of synthetic graphs with power-law degree distributions. We show that Graphine achieves sublinear scalability with the number of cores per node, number of nodes, and graph sizes (up to one billion vertices), and is 2 $\sim$ 15 times faster than the state-of-the-art PowerGraph on a cluster of 16 multicore nodes.
Mohsen Ghaffari - One of the best experts on this subject based on the ideXlab platform.
-
conditional hardness results for massively Parallel Computation from distributed lower bounds
Foundations of Computer Science, 2019Co-Authors: Mohsen Ghaffari, Fabian Kuhn, Jara UittoAbstract:We present the first conditional hardness results for massively Parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively Parallel Computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively Parallel Computation setting.
-
the complexity of δ 1 coloring in congested clique massively Parallel Computation and centralized local Computation
Principles of Distributed Computing, 2019Co-Authors: Yijun Chang, Manuela Fischer, Jara Uitto, Mohsen Ghaffari, Yufan ZhengAbstract:In this paper, we present new randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (Δ+1)-list-coloring, in three well-studied models of distributed, Parallel, and centralized Computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Δ + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log* Δ)-round randomized algorithms of Parter and Su [DISC'18] and O((log log Δ)⋅ log* Δ)-round randomized algorithm of Parter [ICALP'18]. Massively Parallel Computation: We present a randomized (Δ + 1)-list-coloring algorithm with round complexity O(√ log log n ) in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of O(nα) per machine, for any desirable constant α > 0, and a total memory of O (m), where m is the number of edges in the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, an O(1)-round algorithm was given very recently by Assadi et al. [SODA'19]. Centralized Local Computation: We show that (Δ + 1)-list-coloring can be solved by a randomized algorithm with query complexity Δ O(1) … O(log n), in the centralized local Computation model. The previous state of the art for (Δ+1)-list-coloring in the centralized local Computation model are based on simulation of known LOCAL algorithms. The deterministic O(√ Δ poly log Δ + log* n)-round LOCAL algorithm of Fraigniaud et al. [FOCS'16] can be implemented in the centralized local Computation model with query complexity ΔO(√ Δ poly log Δ) … O(log* n); the randomized O(log* Δ) + 2^O(√ log log n)-round LOCAL algorithm of Chang et al. [STOC'18] can be implemented in the centralized local Computation model with query complexity ΔO(log* Δ) … O(log n).
-
sparsifying distributed algorithms with ramifications in massively Parallel Computation and centralized local Computation
Symposium on Discrete Algorithms, 2019Co-Authors: Mohsen Ghaffari, Jara UittoAbstract:We introduce a method for "sparsifying" distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA).• MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic O(log n)-round Parallel (PRAM) counterparts for problems such as Maximal Independent Set (MIS), Maximal Matching, 2-Approximation of Minimum Vertex Cover, and (1 + e)-Approximation of Maximum Matching. Currently, all such MPC algorithms require memory of [MATH HERE] per machine: Czumaj et al. [STOC'18] were the first to handle [MATH HERE] memory, running in O((log log n)2) rounds, who improved on the n1+Ω(1) memory requirement of the O(1)-round algorithm of Lattanzi et al [SPAA'11]. We obtain [MATH HERE]-round MPC algorithms for all these four problems that work even when each machine has strongly sublinear memory, e.g., nα for any constant α ϵ (0, 1). Here, Δ denotes the maximum degree. These are the first sublogarithmic-time MPC algorithms for (the general case of) these problems that break the linear memory barrier.• LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity ΔO(log Δ) poly(log n), by Ghaffari [SODA'16], which improved over the ΔO(log2 Δ) poly(log n) bound of Levi et al. [Algorithmica'17]. As pointed out by Rubinfeld, obtaining a query complexity of poly(Δ log n) remains a central open question. Ghaffari's bound almost reaches a [MATH HERE] barrier common to all known MIS LCAs, which simulate a distributed algorithm by learning the full local topology, a la Parnas-Ron [TCS'07]. There is a barrier because the distributed complexity of MIS has a lower bound of [MATH HERE], by results of Kuhn, et al. [JACM'16], which means this methodology cannot go below query complexity [MATH HERE]. We break this barrier and obtain an LCA for MIS that has a query complexity ΔO(log log Δ) poly(log n).
-
improved massively Parallel Computation algorithms for mis matching and vertex cover
Principles of Distributed Computing, 2018Co-Authors: Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt RubinfeldAbstract:We present O(loglog n) -round algorithms in the Massively Parallel Computation (MPC) model, with O (n) memory per machine, that compute a maximal independent set, a 1+e approximation of maximum matching, and a 2+eapproximation of minimum vertex cover, for any n-vertex graph and any constant \eps>0. These improve the state of the art as follows: Our MIS algorithm leads to a simple O(loglog Δ)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the O (√log Δ )-round algorithm of Ghaffari [PODC'17]. Our O(loglog n)-round (1+e)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log^2log n)-round (1+\eps)-approximation algorithm of Czumaj et al. [STOC'18] and $O(loglog n)-round (1+e)-approximation algorithm of Assadi et al. [arXiv'17]. Our O(loglog n)-round (2+e)-approximate minimum vertex cover algorithm improves on an O(loglog n)-round O(1)-approximation of Assadi et al. [arXiv'17].
-
sparsifying distributed algorithms with ramifications in massively Parallel Computation and centralized local Computation
arXiv: Data Structures and Algorithms, 2018Co-Authors: Mohsen Ghaffari, Jara UittoAbstract:We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). - MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic $O(\log n)$-round Parallel counterparts for problems such as MIS, Maximal Matching, 2-Approximation of Minimum Vertex Cover, and $(1+\epsilon)$-Approximation of Maximum Matching. Currently, all such MPC algorithms require $\tilde{\Omega}(n)$ memory per machine. Czumaj et al. [STOC'18] were the first to handle $\tilde{\Omega}(n)$ memory, running in $O((\log\log n)^2)$ rounds. We obtain $\tilde{O}(\sqrt{\log \Delta})$-round MPC algorithms for all these four problems that work even when each machine has memory $n^{\alpha}$ for any constant $\alpha\in (0, 1)$. Here, $\Delta$ denotes the maximum degree. These are the first sublogarithmic-time algorithms for these problems that break the linear memory barrier. - LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity $\Delta^{O(\log \Delta)} poly(\log n)$, by Ghaffari [SODA'16]. As pointed out by Rubinfeld, obtaining a query complexity of $poly(\Delta\log n)$ remains a central open question. Ghaffari's bound almost reaches a $\Delta^{\Omega\left(\frac{\log \Delta}{\log\log \Delta}\right)}$ barrier common to all known MIS LCAs, which simulate distributed algorithms by learning the local topology, a la Parnas-Ron [TCS'07]. This barrier follows from the $\Omega(\frac{\log \Delta}{\log\log \Delta})$ distributed lower bound of Kuhn, et al. [JACM'16]. We break this barrier and obtain an MIS LCA with query complexity $\Delta^{O(\log\log \Delta)} poly(\log n)$.
