CSE FACULTY SEMINARS

Prof. Syamantak Das, CSE, IIITD

Short Bio:
Syamantak Das is an Assistant Professor in Dept. of CSE at IIIT Delhi. After obtaining his PhD from IIT Delhi, he worked as a visiting post-doc at MPI Informatik, Saarbruecken, Germany followed by another post-doc at the University of Bremen, Germany. His main interest lies in designing algorithms with provable guarantees with a major focus on discrete optimization and graph problems.
http://faculty.iiitd.ac.in/~syamantak/

Date:June 25, 2020
Time: 4:00 PM IST

Graph compression or sparsification is a basic information-theoretic and computational question of the following nature: given a graph G, can we compute a “compact” representation of G, with potentially fewer vertices or edges, that preserves important information? Such objects play a major role in the design of efficient graph algorithms and thus have been a centre of study for decades. For instance, the notion of graph spanners aims to preserve the distance between nodes in the graphs while reducing the number of edges, while the notion of vertex sparsification focuses on preserving some properties of the designated nodes such as connectivity, cut sizes, or effective resistance. In this talk, I shall mostly do a survey of vertex sparsification of graphs and try to establish its connections to various algorithmic problems related to graphs both in the static and the dynamic setting