From the 1 of 8 linked papers with an AI index.
6 papers · 1 filter
Local Certification of Vertex and Edge Connectivity
Yi-Jun Chang, Yi-Xuan Lee, Meng-Tsung Tsai
The paper studies how to verify global vertex and edge connectivity of a graph using only local information, designing certificate schemes with provable size bounds and matching lo…
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…
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…
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…