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

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

TCS Journal 2024 Journal Article

The energy complexity of diameter and minimum cut computation in bounded-genus networks

Yi-Jun Chang

This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximum number of awake rounds of a vertex. Recent works revealed that some problems, such as broadcast, breadth-first search, and maximal matching, can be solved with energy-efficient algorithms that consume only poly log ⁡ n energy. However, there exist some problems, such as computing the diameter of the graph, that require Ω ( n ) energy to solve. To improve energy efficiency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computing the exact diameter, the exact global minimum cut size, and a ( 1 ± ϵ ) -approximate s-t minimum cut size with O ˜ ( n ) energy for bounded-genus graphs. Our approach is based on a generic framework that divides the vertex set into high-degree and low-degree parts and leverages the structural properties of bounded-genus graphs to control the number of certain connected components in the subgraph induced by the low-degree part.

Details DOI

TCS Journal 2023 Journal Article

Distributed graph problems through an automata-theoretic lens

Yi-Jun Chang
Jan Studený
Jukka Suomela

The locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius-T neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem Π, we would like to determine if Π is solvable and what is the asymptotic locality of Π as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving Π. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is PSPACE -hard (Balliu et al. , PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We study locally checkable graph problems from an automata-theoretic perspective by representing a locally checkable problem Π as a nondeterministic finite automaton M over a unary alphabet. We identify polynomial-time-computable properties of the automaton M that near-completely capture the solvability and locality of Π in cycles and paths, with the exception of one specific case that is co- NP -complete.

Details DOI

SODA Conference 2021 Conference Paper

Tight Distributed Listing of Cliques

Keren Censor-Hillel
Yi-Jun Chang
François Le Gall
Dean Leitersdorf

Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few tight bounds are known in this area. For triangle (i. e. , 3-clique) listing, an optimal Õ ( n 1/3 )-round distributed algorithm has been constructed by Chang et al. [SODA 2019, PODC 2019]. Recent works of Eden et al. [DISC 2019] and of Censor-Hillel et al. [PODC 2020] have shown sublinear algorithms for K p -listing, for each p ≥ 4, but still leaving a significant gap between the upper bounds and the known lower bounds of the problem. In this paper, we completely close this gap. We show that for each p ≥ 4, there is an Õ ( n 1–2/ p )-round distributed algorithm that lists all p -cliques K p in the communication network. Our algorithm is optimal up to a polylogarithmic factor, due to the -round lower bound of Fischer et al. [SPAA 2018], which holds even in the CONGESTED CLIQUE model. Together with the triangle-listing algorithm by Chang et al. [SODA 2019, PODC 2019], our result thus shows that the round complexity of K p -listing, for all p, is the same in both the CONGEST and CONGESTED CLIQUE models, at rounds. For p = 4, our result additionally matches the lower bound for K 4 - detection by Czumaj and Konrad [DISC 2018], implying that the round complexities for detection and listing of K 4 are equivalent in the CONGEST model.

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

TCS Journal 2019 Journal Article

Hardness of RNA folding problem with four symbols

Yi-Jun Chang

An RNA sequence is a string composed of four types of nucleotides, A, C, G, and U. The goal of the RNA folding problem is to find a maximum cardinality set of crossing-free pairs of the form { A, U } or { C, G } in a given RNA sequence. The problem is central in bioinformatics and has received much attention over the years. Abboud, Backurs, and Williams (FOCS 2015) demonstrated a conditional lower bound for a generalized version of the RNA folding problem based on a conjectured hardness of the k-clique problem. Their lower bound requires the RNA sequence to have at least 36 types of symbols, making the result not applicable to the RNA folding problem in real life (i. e. , alphabet size 4). In this paper, we present an improved lower bound that works for the alphabet size 4 case. We also investigate the Dyck edit distance problem, which is a string problem closely related to RNA folding. We demonstrate a reduction from RNA folding to Dyck edit distance with alphabet size 10. This leads to a much simpler proof of the conditional lower bound for Dyck edit distance problem given by Abboud, Backurs, and Williams (FOCS 2015), and lowers the alphabet size requirement.

Details DOI

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

STOC Conference 2017 Conference Paper

Exponential separations in the energy complexity of leader election

Yi-Jun Chang
Tsvi Kopelowitz
Seth Pettie
Ruosong Wang
Wei Zhan

Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of Leader Election and Approximate Counting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions . We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.)

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

TCS Journal 2015 Journal Article

Constrained floorplans in 2D and 3D

Yi-Jun Chang
Hsu-Chun Yen

A rectilinear dual of a plane graph refers to a partition of a rectangular area into nonoverlapping rectilinear polygonal modules, where each module corresponds to a vertex such that two modules have a side-contact iff their corresponding vertices are adjacent. An interesting observation is that most algorithms yielding low polygonal complexity rectilinear duals require the use of ⊤-shape modules or their extensions. To justify the intuition that ⊤-shape modules are more powerful than other 8-sided modules, we show the optimum polygonal complexity of ⊤-free rectilinear duals to be exactly 12. Our construction uses only monotone staircase modules. We continue this line of research by studying polygonal complexity and area-universality of rectilinear duals using modules of constrained shapes. Motivated by the design challenges in 3D IC technology, we also study the generalization of rectilinear duals in three dimensions by allowing each module to be an orthogonal polyhedron. Such a generalization to three dimensions opens the door for non-planar graphs to be accommodated in floorplan design. In particular, we prove that all chordal graphs admit 3D floorplans, which parallels the well-known result that all maximal plane graphs admit rectilinear duals.

Details DOI