Vihan Shah 

Marie Curie Fellow at University of Birmingham 

Much of theoretical computer science research over the past several decades has focused on designing fast polynomial time algorithms for graph problems. However, many graphs arising today are so massive that random access queries to the input are expensive. These graphs may contain trillions of edges, making classical algorithmic approaches increasingly impractical for modern large scale graph data.

To address these challenges, researchers have developed modern models of computation that explicitly account for limited access to the input. In this talk, I will discuss how such models provide new ways to process massive graphs. In particular, I will focus on two closely related directions: streaming algorithms, where the graph arrives as a sequence of edges and must be processed using limited memory; and sublinear-time algorithms, which aim to answer graph questions while inspecting only a small portion of the input.

Using fundamental graph problems such as matching and connectivity as examples, I will present my work on streaming and sublinear-time algorithms. In particular, I will discuss results establishing optimal bounds in the streaming model, along with recent work studying adaptivity in sublinear-time graph algorithms, an aspect that has been almost entirely overlooked in the literature.