Dr. Sabyasachi Basu is a postdoctoral researcher at Microsoft Research India, where he works with the vector search team (DiskANN) on problems in quantization and retrieval. He earned his PhD in Computer Science from the University of California, Santa Cruz, where he worked with C. Seshadhri on sublinear algorithms and graph decompositions. Previously, he completed his undergraduate studies in Mathematics at IISc Bangalore. His research interests include using theoretical insights to design algorithms for real-world data and exploring theoretical questions arising from empirical observations.

Decompositions of large-scale networks are central to many applications in graph mining, network science, and algorithm design. Over several decades, a rich body of work has developed techniques to partition networks with various different objectives. However, a noticeable gap persists between methods with strong theoretical guarantees and those that perform well in practice. Practical algorithms often lack provable guarantees, while theoretically sound methods are rarely straightforward to implement and scale poorly.

This talk presents a suite of techniques aimed at bridging this gap, focusing on dense subgraph decomposition — a fundamental problem with numerous real-world applications and a close relation to community detection. We introduce fast, theoretically grounded algorithms that perform efficiently on large datasets, along with new objectives and frameworks that capture structural properties of real-world networks. If time permits, Dr. Basu will also discuss challenges and successes in developing similar algorithms for overlapping clusters.