Sourav Medya successfully defended his PhD on the topic of "Scalable Algorithms for Network Design".

Committee: Ambuj Singh (Chair), Amr El Abbadi, Xifeng Yan, Charu Aggarwal, Prithwish Basu

Abstract: Networks (or graphs) are a powerful tool to model complex systems such as social networks, transportation networks, and the Web. Network design problems, including planning, implementing and augmenting networks for desirable properties, arise naturally in many applications: How to contain fake news in social networks? How to preserve a species by conserving important properties of an ecosystem? How to promote healthier behaviour among individuals via their social interactions? However, characterizing the combinatorial effect of these network modifications leads to challenging optimization problems. From a theoretical standpoint, different from their search counterparts (e.g. computing shortest path), the design problems (e.g. optimizing shortest paths) are computationally hard.

My research focuses on the development of algorithms for solving large-scale real-world problems using network design. In this talk, I will discuss a few network design problems and their solutions. More specifically, I will focus on the influence minimization, resilience maximization, and leader hiding in networks. I will present fast algorithms for these problems using continuous optimization, randomized algorithms and game theoretic techniques. As part of a few recent work, I will also discuss how these combinatorial problems can be solved using deep learning.