Arrow Research search

Author name cluster

Yi-Jun Chang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
2 author rows

Possible papers

13

SODA Conference 2024 Conference Paper

Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs

  • Yi-Jun Chang
  • Da Wei Zheng

We consider the massively parallel computation (MPC) model, which is a theoretical abstraction of large- scale parallel processing models such as MapReduce. In this model, assuming the widely believed 1-vs-2-cycles conjecture, solving many basic graph problems in O (1) rounds with a strongly sublinear memory size per machine is impossible. We improve on the recent work of Holm and Tětek [SODA 2023] that bypass this barrier for problems when a planar embedding of the graph is given. In the previous work, on graphs of size n with O(n/S) machines, the memory size per machine needs to be at least S = n 2/3+Ω(1), whereas we extend their work to the fully scalable regime, where the memory size per machine can be S = n δ for any constant 0 < δ < 1. We thus give the first constant round fully scalable algorithms for embedded planar graphs for the problems of (i) connectivity and (ii) minimum spanning tree (MST). Moreover, we show that the ɛ-emulator of Chang, Krauthgamer, and Tan [STOC 2022] can be incorporated into our recursive framework to obtain constant-round (1 + ɛ)-approximation algorithms for the problems of computing (iii) single source shortest path (SSSP), (iv) global min-cut, and (v) st -max flow. All previous results on cuts and flows required linear memory in the MPC model. Furthermore, our results give new algorithms for problems that implicitly involve embedded planar graphs. We give as corollaries of our result the constant round fully scalable algorithms for (vi) 2D Euclidean MST using O ( n ) total memory and (vii) (1 + ɛ)-approximate weighted edit distance using Õ(n 2-δ ) memory. Our main technique is a recursive framework combined with novel graph drawing algorithms that allow us to compute smaller embedded planar graphs in constant rounds in the fully scalable setting. * The full version of the paper can be accessed at https: //arxiv. org/abs/2304. 07441

Details

FOCS Conference 2020 Conference Paper

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization

  • Yi-Jun Chang
  • Thatchaphol Saranurak

There is a recent exciting line of work in distributed graph algorithms in the CONGEST model that exploit expanders. All these algorithms so far are based on two tools: expander decomposition and expander routing. An ( ε, φ)-expander decomposition removes ε-fraction of the edges so that the remaining connected components have conductance at least φ, i. e. , they are φ-expanders, and expander routing allows each vertex v in a φ-expander to very quickly exchange deg(v) messages with any other vertices, not just its local neighbors. In this paper, we give the first efficient deterministic distributed algorithms for both tools. We show that an ( ε, φ) -expander decomposition can be deterministically computed in poly (ε -1 )n o(1) rounds for φ = poly (ε)n -o(1), and that expander routing can be performed deterministically in poly (φ -1 )n o(1) rounds. Both results match previous bounds of randomized algorithms by [Chang and Saranurak, PODC 2019] and [Ghaffari, Kuhn, and Su, PODC 2017] up to subpolynomial factors. Consequently, we derandomize existing distributed algorithms that exploit expanders. We show that a minimum spanning tree on n -o(1) -expanders can be constructed deterministically in n o(1) rounds, and triangle detection and enumeration on general graphs can be solved deterministically in O(n 0. 58 ) and n 2/3+o(1) rounds, respectively. Using similar techniques, we also give the first polylogarithmic-round randomized algorithm for constructing an ( ε, φ) -expander decomposition in poly (ε -1, logn) rounds for φ = 1/poly(ε -1, logn). This algorithm is faster than the previous algorithm by [Chang and Saranurak, PODC 2019] in all regimes of parameters. The previous algorithm needs n Ω(1) rounds for any φ ≥ 1/polylogn.

Details

SODA Conference 2019 Conference Paper

Distributed Triangle Detection via Expander Decomposition

  • Yi-Jun Chang
  • Seth Pettie
  • Hengjie Zhang

We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in Õ ( n 1/2 ) rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were Õ ( n 2/3 ) and Õ ( n 3/4 ), respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in Õ ( n 1– δ ) rounds we can partition the edge set of the network G = ( V, E ) into three parts E = E m ∪ E s ∪ E r such that Each connected component induced by E m has minimum degree Ω ( n δ ) and conductance Ω(1/polylog( n )). As a consequence the mixing time of a random walk within the component is O (polylog( n )). The subgraph induced by E s has arboricity at most n δ. | E r | ≤ | E |/6. All of our algorithms are based on the following generic framework, which we believe is of interest beyond this work. Roughly, we deal with the set E s by an algorithm that is efficient for low-arboricity graphs, and deal with the set E r using recursive calls. For each connected component induced by E m, we are able to simulate CONGESTED-CLIQUE algorithms with small overhead by applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.

Details

STOC Conference 2018 Conference Paper

An optimal distributed (Δ+1)-coloring algorithm?

  • Yi-Jun Chang
  • Wenzheng Li
  • Seth Pettie

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O (log ∗ n + Det d (poly log n )) time, where Det d ( n ′) is the deterministic complexity of (deg+1)-list coloring ( v ’s palette has size deg( v )+1) on n ′-vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016). with complexity O (√logΔ + loglog n + Det d (poly log n )), and (when Δ is sufficiently large) is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), with complexity O (√Δlog 2.5 Δ + log * n ). Our algorithm appears to be optimal. It matches the Ω(log ∗ n ) randomized lower bound, due to Naor (SIDMA 1991) and sort of matches the Ω(Det(poly log n )) randomized lower bound due to Chang, Kopelowitz, and Pettie (FOCS 2016), where Det is the deterministic complexity of (Δ+1)-list coloring. The best known upper bounds on Det d ( n ′) and Det( n ′) are both 2 O (√log n ′) by Panconesi and Srinivasan (Journal of Algorithms 1996), and it is quite plausible that the complexities of both problems are the same, asymptotically.

Details

SODA Conference 2018 Conference Paper

The Complexity of Distributed Edge Coloring with Small Palettes

  • Yi-Jun Chang
  • Qizheng He
  • Wenzheng Li
  • Seth Pettie
  • Jara Uitto

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. • We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(log Δ log n ) time w. h. p. and Ω(log Δ n ) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. • We give a randomized edge coloring algorithm that can use palette sizes as small as, which is a natural barrier for randomized approaches. The running time of the algorithm is at most O (log Δ · T LLL ), where T LLL is the complexity of a permissive version of the constructive Lovász local lemma. • We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊ )Δ-edge coloring algorithm for trees running in O (log log n ) time. This algorithm arises from two new results: a deterministic O (log n )-time LLL algorithm for tree-structured instances, and a randomized O (log log n )-time graph shattering method for breaking the dependency graph into independent O (log n )-size LLL instances. • A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e. g. , via “augmenting paths. ” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n ). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O (log Δ n )-length augmenting paths.

Details

FOCS Conference 2017 Conference Paper

A Time Hierarchy Theorem for the LOCAL Model

  • Yi-Jun Chang
  • Seth Pettie

The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the classic distributed LOCAL model has been open for many years. In particular, it is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as O(1), O(log* n), O(log n), 2^{O(sqrt{log n}), etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. Our main results are as follows: • We define an infinite set of simple coloring problems called Hierarchical 2½-Coloring. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the k-level Hierarchical 2½-Coloring problem is Θ(n^{1/k}), for positive integer k. The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. • Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized n^{o(1)}-time algorithm solving the LCL can be transformed into a deterministic O(log n)-time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges ω(log* n)—o(log n) or ω(log n)—n^{o(1)}. • We expose a gap in the randomized time hierarchy on general graphs. Roughly speaking, any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in O(T_{LLL}) time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be Ω(log log n) and 2^{O(sqrt{log log n})} on bounded degree graphs. Finally, we revisit Naor and Stockmeyers characterization of O(1)-time LOCAL algorithms for LCL problems (as order-invariant w. r. t. vertex IDs) and calculate the complexity gaps that are directly implied by their proof. For n-rings we see a ω(1)—o(log* n) complexity gap, for (sqrt{n} × √{n})-tori an ω(1)—o(sqrt{log* n}) gap, and for bounded degree trees and general graphs, an ω(1)—o(log(log* n)) complexity gap.

Details

FOCS Conference 2016 Conference Paper

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

  • Yi-Jun Chang
  • Tsvi Kopelowitz
  • Seth Pettie

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. We prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: 1) Building on the recent randomized lower bounds of Brandt et al. [1], we prove that the randomized complexity of Δ-coloring a tree with maximum degree Δ is O(log Δ log n + log*n), for any Δ > = 55, whereas its deterministic complexity is Ω(log Δ n) for any Δ > = 3. This also establishes a large separation between the deterministic complexity of Δ-coloring and (Δ+1)-coloring trees. 2) We prove that any deterministic algorithm for a natural class of problems that runs in O(1) + o(log Δ n) rounds can be transformed to run in O(log*n - log*Δ + 1) rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires Ω(log Δ n) time deterministically. This gives an alternate proof that deterministically Δ-coloring a tree with small Δ takes Ω(log Δ n) rounds. 3) We prove that the randomized complexity of any natural problem on instances of size n is at least its deterministic complexity on instances of size √log n. This shows that a deterministic Ω(log Δ n) lower bound for any problem (Δ-coloring a tree, for example) implies a randomized Ω(log Δ log n) lower bound. It also illustrates that the graph shattering technique employed in recent randomized symmetry breaking algorithms is absolutely essential to the LOCAL model. For example, it is provably impossible to improve the 2O(√log log n) term in the complexities of the best MIS and (Δ+1)-coloring algorithms without also improving the 2O(√log n)-round Panconesi-Srinivasan algorithm.

Details