<!DOCTYPE html>

VIHAN SHAH

About Me

I am a Marie SkΕ‚odowska-Curie Postdoctoral Fellow 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.

I began my undergraduate studies at Mahindra Γ‰cole Centrale and completed my degree at Rutgers-Camden, where I was mentored by Rajiv Gandhi.

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 space, time, adaptivity, 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)
    [Full Version] [conf]

  3. An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication 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

  • Directed Reading Program (DRP) Mentor for Women in Mathematics (WiM) (Winter 2024)
    University of Waterloo
  • Research Experiences for Undergraduates (REU) Mentor (Summer 2023)
    Rutgers University / DIMACS
    Along with my advisor Sepehr Assadi
  • Guest Lecture in Randomized Algorithms (CS 761) (Winter 2025)
    University of Waterloo
  • Yearly Guest Lectures on Sublinear and Streaming Algorithms (Summer 2020-2026)
    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
  • Guest Lecture for Design and Analysis of Algorithms (CS 371) (Fall 2019)
    Rutgers University-Camden
  • Teaching Assistant for Discrete Mathematics (Summer 2019)
    Program in Algorithmic and Combinatorial Thinking (PACT), Princeton University

External Reviewing

Conference Reviews

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

Journal Reviews

TCS Theoretical Computer Science 2026