Shreyas Pai (श्रेयस पै)

There should be a picture of me here...
I am an Assistant Professor in the Department of Computer Science and Engineering at Indian Institute of Technology Madras in Chennai.

I received my PhD in Computer Science at The University of Iowa under the supervision of Prof. Sriram V. Pemmaraju in May 2021. Afterwards I was a post-doctoral fellow at Aalto University hosted by Prof. Jara Uitto till March 2024 (supported by HIIT starting August 2023).

My research interests are primarily in Theory of Distributed and Parallel Computing, more specifically in Distributed Graph Algorithms and Algorithms for Large Data. I am also more generally interested in topics in Theoretical Computer Science like Communication Complexity and Combinatorial Optimization.

During my PhD, I worked as a research assistant in the Computational Epidemiology Group where we try to understand and model the spread of Hospital Acquired Infections (see here for more information).

My ORCID: 0000-0003-2409-7807. And here are links to my arXiv and dblp pages.


Manuscripts

Title Authors Links
Online Locality meets Distributed Quantum Computation Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, Jukka Suomela [arxiv]


Conference Papers

2025

Title Authors Conference Links
Faster Set Cover in the MPC Model Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju, Joshua Sobel ICDCN to appear

2024

Title Authors Conference Links
Adaptive Massively Parallel Coloring in Sparse Graphs Rustam Latypov, Yannic Maus, Shreyas Pai, Jara Uitto PODC [arxiv]
The Message Complexity of Distributed Graph Optimization Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson ITCS [arxiv]
A \((3+\varepsilon)\)-Approximate Correlation Clustering Algorithm in Dynamic Streams Melanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, Jara Uitto SODA [arxiv]

2023

Title Authors Conference Links
Conditionally Optimal Parallel Coloring of Forests Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, Jara Uitto DISC [arxiv]
Time and Space Optimal Massively Parallel Algorithm for the \(2\)-Ruling Set Problem Melanie Cambus, Fabian Kuhn, Shreyas Pai, Jara Uitto DISC [arxiv]
Fast Dynamic Programming in Trees in the MPC Model Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo Särkkä, Jan Studený, Jukka Suomela, Jara Uitto, Hossein Vahidi SPAA [arxiv]
Sinkless Orientation Made Simple Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto SOSA [arxiv]

2022

Title Authors Conference Links
Brief Announcement: Distributed Reconfiguration of Spanning Trees Siddharth Gupta, Manish Kumar, Shreyas Pai SSS [arxiv]
Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets Shreyas Pai, Sriram V. Pemmaraju PODC [arxiv]

2021

Title Authors Conference Links
Can we Break Symmetry with \(o(m)\) Communication? Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson PODC [arxiv] [video]
Risk-aware Temporal Cascade Reconstruction to Detect Asymptomatic Cases Hankyu Jang, Shreyas Pai, Bijaya Adhikari, and Sriram V. Pemmaraju ICDM [paper] [code]

2020

Title Authors Conference Links
Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model Kishore Kothapalli, Shreyas Pai, Sriram V. Pemmaraju FSTTCS [arxiv] [video]
Connectivity Lower Bounds in Broadcast Congested Clique Shreyas Pai, Sriram V. Pemmaraju FSTTCS [arxiv] [video]
Distributed Approximation on Power Graphs Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, Shreyas Pai, Sriram V. Pemmaraju PODC [arxiv] [video]

2019

Title Authors Conference Links
A Constant Approximation for Colorful \(k\)-Center Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, Kasturi Varadarajan ESA [arxiv]
Spatiotemporal clustering of in-hospital Clostridioides difficile infection Shreyas Pai, Philip Polgreen, Alberto Segre, Daniel Sewell, and Sriram V. Pemmaraju ICHE [paper]
Brief Announcement: Connectivity Lower Bounds in Broadcast Congested Clique Shreyas Pai, Sriram V. Pemmaraju PODC [arxiv] [video]

2018

Title Authors Conference Links
Large-Scale Distributed Algorithms for Facility Location with Outliers Tanmay Inamdar, Shreyas Pai, Sriram V. Pemmaraju OPODIS [arxiv]
Near Optimal Clustering in the \(k\)-machine model Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, Sriram V. Pemmaraju ICDCN [arxiv]

2017

Title Authors Conference Links
Symmetry Breaking in the Congest Model: Time– and Message–Efficient Algorithms for Ruling Sets Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson DISC [arxiv]
Brief Announcement: Symmetry Breaking in the Congest Model: Time– and Message–Efficient Algorithms for Ruling Sets Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson PODC [arxiv]


Journal Papers

Title Authors Journal Links
Risk-aware Temporal Cascade Reconstruction to Detect Asymptomatic Cases Hankyu Jang, Shreyas Pai, Bijaya Adhikari, Sriram V. Pemmaraju KAIS 2022 [paper] [code]
Near Optimal Clustering in the \(k\)-machine model Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, Sriram V. Pemmaraju TCS 2021 [paper]


Other Publications

Title Authors Venue Links
On the Role of Congestion in Distributed Complexity Shreyas Pai PhD Thesis 2021 [paper]


Teaching

I'll be teaching CS6025 Sublinear Algorithms in the 2025 even semester.

Past Courses


Contact

Email: shreyas at cse dot (append the IITM website URL to complete the email)
Office: SSB 203, Department of Computer Science and Engineering,
Indian Institute of Technology Madras, Chennai, Tamil Nadu 600036, India.
Phone: +91-44-2257-4395


savesoil.org