Sourav Medya PhD Defense

Thursday, July 25, 2019 - 8:00am to 10:00am
HFH 1152
Scalable Algorithms for Network Design
Sourav Medya
Ambuj Singh (Chair), Amr El Abbadi, Xifeng Yan, Charu Aggarwal, Prithwish Basu


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.

Everyone welcome!