<!DOCTYPE html>

VIHAN SHAH

About Me

I am a postdoctoral researcher at the University of Birmingham, where I work with Sagnik Mukhopadhyay in the Theory of Computation group within the School of Computer Science.

Previously, I completed my PhD at the University of Waterloo in the Algorithms & Complexity Group within the Cheriton School of Computer Science. I was incredibly fortunate to be advised by Sepehr Assadi. Before that, I spent three wonderful years at Rutgers University in the theory group of the CS Department.

My undergraduate studies began at Mahindra École Centrale, where I completed three years of my bachelor’s in Computer Science Engineering before transferring to Rutgers-Camden for my final year. There, I was mentored by Rajiv Gandhi, who first sparked my interest in theoretical computer science.

My research lies in theoretical computer science, where I mainly study graph problems through the lens of modern models of computation. My work primarily focuses on streaming algorithms, while also extending to sublinear-time, dynamic, and learning-augmented models. I am motivated by challenges posed by massive datasets, and I enjoy uncovering the fundamental trade-offs between computational resources such as space, time, and approximation in these modern models of computation.

Photo of Vihan Shah

Collaborators

Publications

  1. Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation PhD Thesis
    [Full Version]

  2. Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries SODA 2026
    (solo-authored student paper)

    This work appears as the final chapter of my thesis.
  3. An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs PODS 2025
    with Sepehr Assadi
    [Full Version] [conf]

  4. Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time AISTATS 2025
    with Vladimir Braverman , Prathamesh Dharangutte , Shreyas Pai , and Chen Wang
    [Full Version] [conf]

  5. Space Complexity of Minimum Cut Problems in Single-Pass Streams ITCS 2025
    with Matthew Ding , Alexandro Garces , Jason Li , Honghao Lin , Jelani Nelson , and David P. Woodruff
    [Full Version] [conf] [talk]

  6. Learning-augmented Maximum Independent Set APPROX 2024
    with Vladimir Braverman , Prathamesh Dharangutte , and Chen Wang
    [Full Version] [conf]

  7. New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification ITCS 2024
    with Prantar Ghosh
    [Full Version] [conf] [talk]

  8. Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost NeurIPS 2023
    with Sepehr Assadi and Chen Wang
    [Full Version] [conf]
    There is a new result on this in my thesis. The conf link also includes a short talk and its slides.
  9. Tight Bounds for Vertex Connectivity in Dynamic Streams SOSA 2023
    with Sepehr Assadi
    [Full Version] [conf] [Long Slides] [Short Slides]

  10. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs ICDT 2023
    with Sepehr Assadi , Nirmit Joshi , and Milind Prabhu
    [Full Version] [conf]

  11. Space Optimal Vertex Cover in Dynamic Streams APPROX 2022
    with Kheeran K. Naidu (student-only paper)
    [Full Version] [conf] [talk] [Long Slides] [Short Slides]

  12. An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams ITCS 2022
    with Sepehr Assadi
    [Full Version] [conf] [Long Talk] [Conf Talk] [Long Slides] [Short Slides]

Talks

Service

Teaching

  • Research Experiences for Undergraduates (REU) Mentor (Summer 2023)
    Rutgers University / DIMACS
    Along with my advisor Sepehr Assadi.
  • Directed Reading Program (DRP) Mentor for Women in Mathematics (WiM) (Winter 2024)
    University of Waterloo
  • Guest Lecture in Randomized Algorithms (CS 761) (Winter 2025)
    University of Waterloo
  • Guest Lectures on Sublinear and Streaming Algorithms (Summer 2020–2024)
    Program in Algorithmic and Combinatorial Thinking (PACT), Princeton University
  • Teaching Assistant for Design and Analysis of Computer Algorithms (CS 344) (Spring 2021, Spring 2022, Fall 2021)
    Rutgers University
  • Teaching Assistant for Introduction to Discrete Structures (CS 205) (Fall 2020, Summer 2021)
    Rutgers University
  • Teaching Assistant for Discrete Mathematics (Summer 2019)
    Program in Algorithmic and Combinatorial Thinking (PACT), Princeton University

External Reviews

  • Symposium on Theory of Computing (STOC): 2022, 2024, 2025
  • Symposium on Foundations of Computer Science (FOCS): 2025
  • Symposium on Discrete Algorithms (SODA): 2022, 2023, 2024, 2026
  • Innovations in Theoretical Computer Science (ITCS): 2024, 2025, 2026
  • Symposium on Principles of Database Systems (PODS): 2025
  • Symposium on Simplicity in Algorithms (SOSA): 2026
  • European Symposium on Algorithms (ESA): 2022, 2023, 2024, 2025
  • International Colloquium on Automata, Languages, and Programming (ICALP): 2023, 2025
  • International Symposium on Algorithms and Computation (ISAAC): 2025
  • Symposium on Principles of Distributed Computing (PODC): 2021