Professor Sriram Pemmaraju, Emeritus Faculty Sukumar Ghosh, and UI Alum Shreyas Pai along side computer science PhD students Hongyan Ji and Joshua Sobel recently won the Best Paper in Distributed Computing Track award for their paper “Faster Set Cover in the MPC Model” at the ICDCN 2025 conference.
They present the first O(log N)-round and O(log^1.5 N)-round algorithms in the linear-memory and low-memory MPC models respectively for the classical SetCover problem. Their discovery was achieved by using the technique of sparsified graph exponentiation, that was used to get MPC algorithms for MIS and 2-ruling sets--making their algorithm more efficient.
Impressive progress has been made on de-randomizing MPC algorithms for MIS and coloring. Follow-up work that they hope to achieve is designing a fast MPC algorithm for generalizations of SetCover such as partial SetCover, capacitated SetCover, multi-SetCover, etc.
"It is definitely difficult to do research, and many times it can be frustrating especially if there is no progress visible. But the key is to remain consistent and open to all the possibilities. Progress happens just one "aha!" moment at a time." - Shreyas Pai (21PhD)
Related news:
- Hongyan Ji presented "Enhancing Distributed Algorithms with Local Knowledge" at our 2024 Graduate Research Symposium
- Josh Sobel was awarded a Graduate College Post-Comprehensive Research Fellowship for Spring 2025.
