7 Search Results for "Su, Hsin-Hao"


Document
Adaptive Massively Parallel Constant-Round Tree Contraction

Authors: MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, and Hsin-Hao Su

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Miller and Reif’s FOCS'85 [Gary L. Miller and John H. Reif, 1989] classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additionally it is also used as an algorithmic design technique for a large number of parallel graph algorithms. In all previously explored models of computation, however, tree contractions have only been achieved in Ω(log n) rounds of parallel run time. In this work, we not only introduce a generalized tree contraction method but also show it can be computed highly efficiently in O(1/ε³) rounds in the Adaptive Massively Parallel Computing (AMPC) setting, where each machine has O(n^ε) local memory for some 0 < ε < 1. AMPC is a practical extension of Massively Parallel Computing (MPC) which utilizes distributed hash tables [MohammadHossein Bateni et al., 2017; Behnezhad et al., 2019; Raimondas Kiveris et al., 2014]. In general, MPC is an abstract model for MapReduce, Hadoop, Spark, and Flume which are currently widely used across industry and has been studied extensively in the theory community in recent years. Last but not least, we show that our results extend to multiple problems on trees, including but not limited to maximum and maximal matching, maximum and maximal independent set, tree isomorphism testing, and more.

Cite as

MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, and Hsin-Hao Su. Adaptive Massively Parallel Constant-Round Tree Contraction. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 83:1-83:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hajiaghayi_et_al:LIPIcs.ITCS.2022.83,
  author =	{Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed and Su, Hsin-Hao},
  title =	{{Adaptive Massively Parallel Constant-Round Tree Contraction}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{83:1--83:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.83},
  URN =		{urn:nbn:de:0030-drops-156790},
  doi =		{10.4230/LIPIcs.ITCS.2022.83},
  annote =	{Keywords: Adaptive Massively Parallel Computation, Tree Contraction, Matching, Independent Set, Tree Isomorphism}
}
Document
Distributed Dense Subgraph Detection and Low Outdegree Orientation

Authors: Hsin-Hao Su and Hoa T. Vu

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
The densest subgraph problem, introduced in the 80s by Picard and Queyranne [Networks 1982] as well as Goldberg [Tech. Report 1984], is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. Suppose G = (V,E) is the underlying network as well as the input graph. Let D denote the density of the maximum density subgraph of G. Our main results are as follows. - Given a value D̃ ≤ D and 0 < ε < 1, we show that a subgraph with density at least (1-ε)D̃ can be identified deterministically in O((log n) / ε) rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an O(log n) factor. In the CONGEST~ model, we show that such a subgraph can be identified in O((log³ n) / ε³) rounds with high probability. Our techniques also lead to an O(diameter + (log⁴ n)/ε⁴)-round algorithm that yields a 1-ε approximation to the densest subgraph. This improves upon the previous O(diameter /ε ⋅ log n)-round algorithm by Das Sarma et al. [DISC 2012] that only yields a 1/2-ε approximation. - Given an integer D̃ ≥ D and Ω(1/D̃) < ε < 1/4, we give a deterministic, Õ((log² n) /ε²)-round algorithm in the CONGEST~ model that computes an orientation where the outdegree of every vertex is upper bounded by (1+ε)D̃. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in Õ((log⁶ n)/ ε⁴) rounds and Õ((log³ n) /ε³) rounds respectively and only work in the LOCAL model.

Cite as

Hsin-Hao Su and Hoa T. Vu. Distributed Dense Subgraph Detection and Low Outdegree Orientation. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{su_et_al:LIPIcs.DISC.2020.15,
  author =	{Su, Hsin-Hao and Vu, Hoa T.},
  title =	{{Distributed Dense Subgraph Detection and Low Outdegree Orientation}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.15},
  URN =		{urn:nbn:de:0030-drops-130938},
  doi =		{10.4230/LIPIcs.DISC.2020.15},
  annote =	{Keywords: Distributed Algorithms, Network Algorithms}
}
Document
Estimating Hourly Population Distribution Patterns at High Spatiotemporal Resolution in Urban Areas Using Geo-Tagged Tweets and Dasymetric Mapping

Authors: Jaehee Park, Hao Zhang, Su Yeon Han, Atsushi Nara, and Ming-Hsiang Tsou

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)


Abstract
This paper introduces a spatiotemporal analysis framework for estimating hourly changing population distribution patterns in urban areas using geo-tagged tweets (the messages containing users’ geospatial locations), land use data, and dasymetric maps. We collected geo-tagged social media (tweets) within the County of San Diego during one year (2015) by using Twitter’s Streaming Application Programming Interfaces (APIs). A semi-manual Twitter content verification procedure for data cleaning was applied first to separate tweets created by humans from non-human users (bots). The next step was to calculate the number of unique Twitter users every hour within census blocks. The final step was to estimate the actual population by transforming the numbers of unique Twitter users in each census block into estimated population densities with spatial and temporal factors using dasymetric maps. The temporal factor was estimated based on hourly changes of Twitter messages within San Diego County, CA. The spatial factor was estimated by using the dasymetric method with land use maps and 2010 census data. Comparing to census data, our methods can provide better estimated population in airports, shopping malls, sports stadiums, zoo and parks, and business areas during the day time.

Cite as

Jaehee Park, Hao Zhang, Su Yeon Han, Atsushi Nara, and Ming-Hsiang Tsou. Estimating Hourly Population Distribution Patterns at High Spatiotemporal Resolution in Urban Areas Using Geo-Tagged Tweets and Dasymetric Mapping. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.GIScience.2021.I.10,
  author =	{Park, Jaehee and Zhang, Hao and Han, Su Yeon and Nara, Atsushi and Tsou, Ming-Hsiang},
  title =	{{Estimating Hourly Population Distribution Patterns at High Spatiotemporal Resolution in Urban Areas Using Geo-Tagged Tweets and Dasymetric Mapping}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.10},
  URN =		{urn:nbn:de:0030-drops-130456},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.10},
  annote =	{Keywords: Population Estimation, Twitter, Social Media, Dasymetric Map, Spatiotemporal}
}
Document
RANDOM
Palette Sparsification Beyond (Δ+1) Vertex Coloring

Authors: Noga Alon and Sepehr Assadi

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every n-vertex graph G with maximum degree Δ, sampling O(log n) colors per each vertex independently from Δ+1 colors almost certainly allows for proper coloring of G from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for (Δ+1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we focus on palette sparsification beyond (Δ+1) coloring, in both regimes when the number of available colors is much larger than (Δ+1), and when it is much smaller. In particular, - We prove that for (1+ε) Δ coloring, sampling only O_ε(√{log n}) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1+ε) Δ and (Δ+1) coloring in the context of palette sparsification. - A natural family of graphs with chromatic number much smaller than (Δ+1) are triangle-free graphs which are O(Δ/ln Δ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(Δ^γ + √{log n}) colors per vertex is sufficient and necessary to obtain a proper O_γ(Δ/ln Δ) coloring of triangle-free graphs. - We also consider the "local version" of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling O_ε(log n) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1+ε) ⋅ deg(v) arbitrary colors, or even only deg(v)+1 colors when the lists are the sets {1,…,deg(v)+1}. Our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.

Cite as

Noga Alon and Sepehr Assadi. Palette Sparsification Beyond (Δ+1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.APPROX/RANDOM.2020.6,
  author =	{Alon, Noga and Assadi, Sepehr},
  title =	{{Palette Sparsification Beyond (\Delta+1) Vertex Coloring}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.6},
  URN =		{urn:nbn:de:0030-drops-126096},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.6},
  annote =	{Keywords: Graph coloring, palette sparsification, sublinear algorithms, list-coloring}
}
Document
Track A: Algorithms, Complexity and Games
Lower Bounds for Dynamic Distributed Task Allocation

Authors: Hsin-Hao Su and Nicole Wein

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task. The goal of the agents is to cooperatively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes over time. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead. We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [Su et al., 2017], which can be reformulated as a question of finding a low distortion embedding from symmetric difference to Hamming distance. In this model it is trivial to prove that the switching cost is at least 2. We present the first non-trivial lower bounds for the switching cost, by giving lower bounds of 3 and 4 for different ranges of the parameters.

Cite as

Hsin-Hao Su and Nicole Wein. Lower Bounds for Dynamic Distributed Task Allocation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{su_et_al:LIPIcs.ICALP.2020.99,
  author =	{Su, Hsin-Hao and Wein, Nicole},
  title =	{{Lower Bounds for Dynamic Distributed Task Allocation}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.99},
  URN =		{urn:nbn:de:0030-drops-125063},
  doi =		{10.4230/LIPIcs.ICALP.2020.99},
  annote =	{Keywords: distributed task allocation, combinatorics, lower bounds, multi-agent systems, low-distortion embedding, dynamic algorithms, biological distributed algorithms}
}
Document
Distributed Data Summarization in Well-Connected Networks

Authors: Hsin-Hao Su and Hoa T. Vu

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph G of n nodes each of which may hold a value initially, we focus on computing sum_{i=1}^N g(f_i), where f_i is the number of occurrences of value i and g is some fixed function. This includes important statistics such as the number of distinct elements, frequency moments, and the empirical entropy of the data. In the CONGEST~ model, a simple adaptation from streaming lower bounds shows that it requires Omega~(D+ n) rounds, where D is the diameter of the graph, to compute some of these statistics exactly. However, these lower bounds do not hold for graphs that are well-connected. We give an algorithm that computes sum_{i=1}^{N} g(f_i) exactly in {tau_{G}} * 2^{O(sqrt{log n})} rounds where {tau_{G}} is the mixing time of G. This also has applications in computing the top k most frequent elements. We demonstrate that there is a high similarity between the GOSSIP~ model and the CONGEST~ model in well-connected graphs. In particular, we show that each round of the GOSSIP~ model can be simulated almost perfectly in O~({tau_{G}}) rounds of the CONGEST~ model. To this end, we develop a new algorithm for the GOSSIP~ model that 1 +/- epsilon approximates the p-th frequency moment F_p = sum_{i=1}^N f_i^p in O~(epsilon^{-2} n^{1-k/p}) rounds , for p >= 2, when the number of distinct elements F_0 is at most O(n^{1/(k-1)}). This result can be translated back to the CONGEST~ model with a factor O~({tau_{G}}) blow-up in the number of rounds.

Cite as

Hsin-Hao Su and Hoa T. Vu. Distributed Data Summarization in Well-Connected Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{su_et_al:LIPIcs.DISC.2019.33,
  author =	{Su, Hsin-Hao and Vu, Hoa T.},
  title =	{{Distributed Data Summarization in Well-Connected Networks}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.33},
  URN =		{urn:nbn:de:0030-drops-113400},
  doi =		{10.4230/LIPIcs.DISC.2019.33},
  annote =	{Keywords: Distributed Algorithms, Network Algorithms, Data Summarization}
}
Document
Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

Authors: Merav Parter and Hsin-Hao Su

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)


Abstract
(Delta+1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information. In a recent breakthrough, Yi-Jun Chang, Wenzheng Li, and Seth Pettie [CLP-STOC'18] presented a randomized (Delta+1)-list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)-list coloring algorithm on n'-vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})). Merav Parter [P-ICALP'18] recently provided a randomized (Delta+1)-coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almost-independent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)-coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [Parter-ICALP'18], and a palette sampling technique adopted to the CLP framework.

Cite as

Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{parter_et_al:LIPIcs.DISC.2018.39,
  author =	{Parter, Merav and Su, Hsin-Hao},
  title =	{{Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.39},
  URN =		{urn:nbn:de:0030-drops-98286},
  doi =		{10.4230/LIPIcs.DISC.2018.39},
  annote =	{Keywords: Distributed Graph Algorithms, Coloring, congested clique}
}
  • Refine by Author
  • 5 Su, Hsin-Hao
  • 2 Vu, Hoa T.
  • 1 Alon, Noga
  • 1 Assadi, Sepehr
  • 1 Hajiaghayi, MohammadTaghi
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Graph algorithms
  • 2 Networks → Network algorithms
  • 1 Human-centered computing → Social media
  • 1 Mathematics of computing → Graph coloring
  • Show More...

  • Refine by Keyword
  • 2 Distributed Algorithms
  • 2 Network Algorithms
  • 1 Adaptive Massively Parallel Computation
  • 1 Coloring
  • 1 Dasymetric Map
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 4 2020
  • 1 2018
  • 1 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail