Chhaya Trehan

Computer Scientist

I am a computer scientist. Until very recently I was posted as a postdoctoral fellow at University of Birmimngham. I completed my PhD in Mathematics from London School of Economics & Political Science in 2023. I also have an MSc degree in Information Management & Engineering from Technion, Israel Institute of Technology, Israel. In the final year of my PhD I worked as a Research Assistant/Associate at University of Bristol.

I am interested in algorithms and resource lower bounds for graph problems on large and dynamic graphs arising in real world applications. Specifically, I am interested in graph algorithms in computing models such as (dynamic) streaming, (dynamic) distributed computing and (edge) query model of property testing. All these models allow only a limited view of the input graph to the algorithm at any given time. The algorithms designed for these models are inherently sublinear in the size of the input.

In addition, I also work on the fundamental problems of computing multi-source reachability and approximate shortest paths in the traditional centralized sequential model.

Selected Research Outcomes

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Michael Elkin and Chhaya Trehan

Under Submission

Constructing Long Paths in Graph Streams

Christian Konrad and Chhaya Trehan

Accepted at ESA 2025

All You Need are Random Walks: Fast and Simple Distributed Conductance Testing

Tugkan Batu, Amitabh Trehan and Chhaya Trehan

SIROCCO 2024

When You Come at the King You Best Not Miss

Oded Lachish, Felix Reidl, Chhaya Trehan