🔍 Currently seeking postdoctoral positions.


I am a fifth-year PhD student at the University of Waterloo in the Algorithms & Complexity Group within the Cheriton School of Computer Science. I am incredibly fortunate to be advised by Sepehr Assadi. Before this, I spent three wonderful years at Rutgers University in the theory group of the CS Department. Prior to this, I was a Computer Science major at Rutgers Camden for one year, where I was mentored by Rajiv Gandhi. I completed three years of my bachelor's in Computer Science Engineering at Mahindra École Centrale before transferring to Rutgers Camden.

My research interest is in Theoretical Computer Science and specifically in Streaming Algorithms. I have recently also worked on Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy working on Graph problems in the these settings.
Photo of Vihan Shah

Collaborators

Preprints

Publications

Click on each title for more information:

  1. Space Complexity of Minimum Cut Problems in Single-Pass Streams ITCS 2025
    Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff

  2. Learning-augmented Maximum Independent Set APPROX 2024
    Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang

  3. New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification ITCS 2024
    Prantar Ghosh, Vihan Shah

  4. Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost NeurIPS 2023
    Sepehr Assadi, Vihan Shah, Chen Wang

  5. Tight Bounds for Vertex Connectivity in Dynamic Streams SOSA 2023
    Sepehr Assadi, Vihan Shah

  6. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs ICDT 2023
    Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah

  7. Space Optimal Vertex Cover in Dynamic Streams APPROX 2022
    Kheeran K. Naidu, Vihan Shah

  8. An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams ITCS 2022
    Sepehr Assadi, Vihan Shah

Service

Teaching

  • Research Experiences for Undergraduates (REU) Mentor (Summer 23)
    Along with my advisor Sepehr Assadi at Rutgers University/DIMACS.
  • Directed Reading Program (DRP) Mentor for Women in Mathematics (WiM) (Winter 24)
    University of Waterloo
  • Guest Lectures on Sublinear and Streaming Algorithms (Summer 20, 21, 22, 23, 24)
    Program in Algorithmic and Combinatorial Thinking (PACT), Princeton University.
  • Teaching Assistant for Design and Analysis of Computer Algorithms (CS 344) (Spring 21, 22, Fall 21)
    Rutgers University.
  • Teaching Assistant for Introduction to Discrete Structures (CS 205) (Fall 20, Summer 21)
    Rutgers University.
  • Teaching Assistant for Discrete Mathematics (Summer 19)
    Program in Algorithmic and Combinatorial Thinking (PACT), Princeton University.

External Reviews

  • Symposium on Theory of Computing (STOC): 2022, 2024
  • Symposium on Discrete Algorithms (SODA): 2022, 2023, 2024
  • Innovations in Theoretical Computer Science (ITCS): 2024
  • European Symposium on Algorithms (ESA): 2022, 2023, 2024
  • International Colloquium on Automata, Languages, and Programming (ICALP): 2023
  • Symposium on Principles of Distributed Computing (PODC): 2021