Shreyas Pai

There should be a picture of me here...

I received my PhD in Computer Science at The University of Iowa under the supervision of Prof. Sriram Pemmaraju in Spring 2021. I am joining the Theory group at Aalto University as a postdoc in Fall 2021.

My research interests generally lie in Theoretical Computer Science, more specifically in Distributed Algorithms, Communication Complexity, and Combinatorial Optimization.

During my PhD, I was a research assistant in the Computational Epidemiology Group where I worked on understanding and modeling the spread of Hospital Acquired Infections (see here for more information).

Here is my CV. And these are links to my arXiv and dblp pages.


  • Can we Break Symmetry with \(o(m)\) Communication? [paper]
    • with Gopal Pandurangan, Sriram Pemmaraju, and Peter Robinson
    • PODC 2021
  • Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model [paper]
    • with Kishore Kothapalli and Sriram Pemmaraju
    • FSTTCS 2020
  • Distributed Approximation on Power Graphs [paper]
    • with Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, and Sriram Pemmaraju
    • PODC 2020
  • Spatiotemporal clustering of in-hospital Clostridioides difficile infection [paper]
    • with Philip Polgreen, Alberto Segre, Daniel Sewell, and Sriram Pemmaraju
    • Infection Control and Hospital Epidemiology 2019
  • A Constant Approximation for Colorful \(k\)-Center [paper]
    • with Sayan Bandyapadhyay, Tanmay Inamdar, and Kasturi Varadarajan
    • ESA 2019
  • Connectivity Lower Bounds in Broadcast Congested Clique [paper]
    • with Sriram Pemmaraju
    • PODC 2019 (Brief Announcement) and FSTTCS 2020
  • Large-Scale Distributed Algorithms for Facility Location with Outliers [paper]
    • with Tanmay Inamdar, and Sriram Pemmaraju
    • OPODIS 2018
  • Near Optimal Clustering in the \(k\)-machine model [paper]
    • with Sayan Bandyapadhyay, Tanmay Inamdar, and Sriram Pemmaraju
    • ICDCN 2018
  • Symmetry Breaking in the Congest Model: Time– and Message–Efficient Algorithms for Ruling Sets [paper]
    • with Gopal Pandurangan, Sriram Pemmaraju, Talal Riaz, and Peter Robinson
    • PODC 2017 (Brief Announcement) and DISC 2017


  • Spring 2020: TA for CS:4330 Theory of Computation
  • Spring 2017: Instructor for CS:3330 Algorithms, Section 2
  • Fall 2016: TA for CS:1210 Computer Science 1: Fundamentals


Office: 101C, MacLean Hall, Iowa City, IA 52242-1419 (good luck finding me here)