Hongyan Ji

2026

1. DISC

   Approximating Minimum Dominating Set with Few Awake Rounds

   Hongyan Ji, Shreyas Pai, and Sriram V. Pemmaraju

   In 40th International Symposium on Distributed Computing, 2026

   To appear at DISC 2026

   Abstract arXiv Citation

   We study Minimum Dominating Set in the sleeping CONGEST model, where nodes may sleep and can compute or communicate only while awake. We give the first O(log Δ)-approximation algorithm with o(log² Δ) awake complexity: it runs in O(log² Δ) rounds with Õ(log Δ) awake complexity. We also establish a trade-off between approximation quality and awake complexity.

   @inproceedings{ji2026approximating,
     author = {Ji, Hongyan and Pai, Shreyas and Pemmaraju, Sriram V.},
     title = {Approximating Minimum Dominating Set with Few Awake Rounds},
     booktitle = {40th International Symposium on Distributed Computing},
     year = {2026},
     note = {To appear at DISC 2026},
     keywords = {Distributed Algorithms, Sleeping CONGEST, Awake Complexity, Minimum Dominating Set, Approximation Algorithms},
   }

2. TCS

   Faster Set Cover in the MPC Model

   Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju, and Joshua Sobel

   Theoretical Computer Science, 2026

   Journal version; Volume 1086, Article 116238

   Abstract DOI Citation PDF

   The Massively Parallel Computation (MPC) model is a popular abstraction for large-scale distributed computing. For Set Cover with n elements and m sets, we give two O(log n)-approximation algorithms. They run in Õ(log N) rounds in the linear-memory MPC model and Õ(log¹·⁵ N) rounds in the sublinear-memory MPC model, where N = n + m. These are the first O(log n)-approximation algorithms for Set Cover in this setting that run in o(log² N) rounds.

   @article{ji2026faster,
     author = {Ji, Hongyan and Pai, Shreyas and Pemmaraju, Sriram V. and Sobel, Joshua},
     title = {Faster Set Cover in the MPC Model},
     journal = {Theoretical Computer Science},
     volume = {1086},
     pages = {116238},
     year = {2026},
     issn = {0304-3975},
     doi = {10.1016/j.tcs.2026.116238},
     url = {https://doi.org/10.1016/j.tcs.2026.116238},
     note = {Journal version; Volume 1086, Article 116238},
     keywords = {Parallel Set Cover, Massively Parallel Computation, Approximation Algorithms},
   }

2025

1. ICDCN

   Fast Deterministic Massively Parallel Ruling Sets Algorithms

   Hongyan Ji, Kishore Kothapalli, Sriram V. Pemmaraju, and Ajitanshu Singh

   In Proceedings of the 26th International Conference on Distributed Computing and Networking, 2025

   Abstract DOI Citation PDF

   We give a deterministic Õ((log Δ)^(1/3))-round algorithm for the 2-ruling set problem in the sublinear-memory MPC model, improving on the previous Õ(sqrt(log n))-round bound. The result derandomizes the sample-and-gather approach, which requires fixing randomness for a batch of future iterations. We extend the approach to β-ruling sets and to bounded-arboricity graphs.

   @inproceedings{ji2025rulingsets,
     author = {Ji, Hongyan and Kothapalli, Kishore and Pemmaraju, Sriram V. and Singh, Ajitanshu},
     title = {Fast Deterministic Massively Parallel Ruling Sets Algorithms},
     booktitle = {Proceedings of the 26th International Conference on Distributed Computing and Networking},
     series = {ICDCN '25},
     pages = {152--160},
     numpages = {9},
     year = {2025},
     isbn = {9798400710629},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     doi = {10.1145/3700838.3700872},
     url = {https://doi.org/10.1145/3700838.3700872},
     keywords = {Derandomization, Deterministic Algorithms, Distributed Algorithms, Massively Parallel Computation, Ruling Sets},
   }

2024

1. SIROCCO

   Towards Singular Optimality in the Presence of Local Initial Knowledge

   Hongyan Ji, and Sriram V. Pemmaraju

   In International Colloquium on Structural Information and Communication Complexity, 2024

   Abstract DOI Citation PDF

   The Knowledge Till ρ (KT-ρ) CONGEST model gives each node initial knowledge of its radius-ρ neighborhood. We show that radius-2 initial knowledge substantially improves the round-message trade-off for constructing a sparse communication backbone, or danner. The construction yields improved algorithms for broadcast, leader election, spanning tree, minimum spanning tree, and coloring in the KT-2 CONGEST model.

   @inproceedings{ji2024towards,
     author = {Ji, Hongyan and Pemmaraju, Sriram V.},
     title = {Towards Singular Optimality in the Presence of Local Initial Knowledge},
     booktitle = {International Colloquium on Structural Information and Communication Complexity},
     pages = {300--317},
     year = {2024},
     organization = {Springer},
     doi = {10.1007/978-3-031-60603-8_17},
     url = {https://doi.org/10.1007/978-3-031-60603-8_17},
   }