From the 1 of 4 linked papers with an AI index.
4 papers
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…
Improved All-Pairs Approximate Shortest Paths in Congested Clique
Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang +2
In this paper, we present a new randomized -approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $O(\log \l…
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…