Zi Song Yeoh
PhD Student
Department of Computer Science, Boston University
Department of Computer Science, Boston University
I am a second-year Ph.D. student at Boston University in theoretical computer science. My advisors are Krzysztof Onak and Nathan Klein. I am interested in most fields of theoretical computer science, with a focus on graph algorithms. My current research interests include sublinear algorithms and approximation algorithms.
| Paper | Description | Coauthors | Year |
|---|---|---|---|
| Thin Trees for Near Minimum Cuts | We show that every k-edge-connected graph contains a tree which is O(1/k)-thin with respect to its near minimum cuts. In other words, we construct a tree with at most O(1) edges across every near minimum cut of the graph. | Nathan Klein and Neil Olver | ICALP 2026 |
| Exponential Energy Savings in Local Distributed Graph Algorithms | We investigate the energy complexity of several wellstudied (local) problems in distributed graph algorithms - namely, matching and vertex cover approximations, spanners, low-outdegree, orientations, and set cover. We present randomized distributed algorithms that, while having round complexity almost matching the respective state of the art, achieve nearly exponentially smaller energy complexity. That is, in each of these algorithms, each node is awake for only an exponentially small fraction of the time, and the round complexity still remains almost the same as the best-known algorithm. During the rest of the rounds, the node does not perform any computation or communication (and any messages sent to it at that time go unheard). | Mohsen Ghaffari | SPAA 2026 |
Email: zscoder@bu.edu