Publications in distributed and massively parallel algorithms.
I design resource-efficient distributed and massively parallel algorithms, studying how constraints on communication, memory, randomness, initial knowledge, and energy shape algorithms for graph problems and combinatorial optimization. Preprints and open-access copies are linked below when available.
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},}
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},}
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},}
For Set Cover with n elements and m sets, we give O(log n)-approximation algorithms that 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. We obtain these results by adapting sparsified graph exponentiation, previously used for maximal independent set, to a distributed Set Cover algorithm.
@inproceedings{ji2025setcover,author={Ji, Hongyan and Pai, Shreyas and Pemmaraju, Sriram V. and Sobel, Joshua},title={Faster Set Cover in the MPC Model},booktitle={Proceedings of the 26th International Conference on Distributed Computing and Networking},series={ICDCN '25},pages={144--151},numpages={8},year={2025},isbn={9798400710629},publisher={Association for Computing Machinery},address={New York, NY, USA},doi={10.1145/3700838.3700861},url={https://doi.org/10.1145/3700838.3700861},note={Conference version},keywords={Parallel Set Cover, Massively Parallel Computation, Approximation Algorithms},award={Best Paper Award, Distributed Computing Track, ICDCN 2025},}
Best Paper Award, Distributed Computing Track, ICDCN 2025
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},}