3 citations · 7 across the 8 of their papers we have counts for
9 papers · 1 filter
Improved Massively Parallel Shortest Path Computation
Yi-Jun Chang, Shaun Quek
We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct…
Introvert Clustering for Distributed Graph Algorithms
Yi-Jun Chang, Nima Dolatabadi
We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at le…
A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching
Yi-Jun Chang, Kushagra Chatterjee
We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs using only a few shared random bits. Specifically, in the $\c…
Local Certification of Vertex and Edge Connectivity
Yi-Jun Chang, Yi-Xuan Lee, Meng-Tsung Tsai
Local certification is a framework for verifying global graph properties using only local information. In this model, a prover assigns short labels, called certificates, to the ver…
Bounded Memory in Distributed Networks
Ran Ben Basat, Keren Censor-Hillel, Yi-Jun Chang +3
The recent advent of programmable switches makes distributed algorithms readily deployable in real-world datacenter networks. However, there are still gaps between theory and pract…
Optimal local certification on graphs of bounded pathwidth
Dan Alden Baterisna, Yi-Jun Chang
We present proof labeling schemes for graphs with bounded pathwidth that can decide any graph property expressible in monadic second-order (MSO) logic using -bit vertex…
Deterministic Expander Routing: Faster and More Versatile
Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su
We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is…
Fast Broadcast in Highly Connected Networks
Shashwat Chandra, Yi-Jun Chang, Michal Dory +2
We revisit the classic broadcast problem, wherein we have messages, each composed of bits, distributed arbitrarily across a network. The objective is to broadcast…
Universally Optimal Information Dissemination and Shortest Paths in the HYBRID Distributed Model
Yi-Jun Chang, Oren Hecht, Dean Leitersdorf +1
In this work we consider the HYBRID model of distributed computing, introduced recently by Augustine, Hinnenthal, Kuhn, Scheideler, and Schneider (SODA 2020), where nodes have acce…