IC Colloquium: Algorithmic Paradigms for Dynamic Graph Problems
Event details
| Date | 23.04.2020 |
| Hour | 14:00 › 15:00 |
| Category | Conferences - Seminars |
The talk will take place via zoom. Please click on the following link: https://epfl.zoom.us/j/380717737
By: Thatchaphol Saranurak - Toyota Technological Institute at Chicago
IC Faculty candidate
Abstact
In the traditional view of computation, a computational task is solved from scratch, and then remains solved forever. It is increasingly clear that this static model does not adequately capture the requirements of real-world computation. For instance, in a communication network, new links appear and disappear all the time. Recomputing everything from scratch (to obtain, for instance, connectivity-information about the network) is clearly wasteful. Similar dynamic scenarios arise in most modern applications, including load balancing in parallel computation, tracking communities in social networks, financial fraud detection, and routing.
Dynamic graph algorithms aim to address this issue; they maintain information about graphs that undergo edge/vertex updates without recomputing everything from scratch after each update.
These algorithms are promising for all the practical applications mentioned above and have deep theoretical applications. Unfortunately, even the most basic graph problems, such as graph connectivity and shortest paths, are still not well-understood in the dynamic setting.
In this talk, I will talk about two general techniques recently used to break decades-old barriers on many dynamic graph problems: 1) dynamic expander decomposition and 2) local clustering.
The new development of these techniques on dynamic graphs, in turn, leads to exciting applications even in the classical static setting. For example, they improve the 50-year-old quadratic time bound for checking k-vertex-connectivity to nearly linear time.
Bio
Thatchaphol Saranurak is a theoretical computer scientist, currently holding a research assistant professor position at Toyota Technological Institute at Chicago, USA.
He completed his Ph.D. at KTH Royal Institute of Technology in 2018 where he was supervised by Danupon Nanongkai.
His main research interest is on graph algorithms with a current focus on dynamic, local, and distributed algorithms.
More information
By: Thatchaphol Saranurak - Toyota Technological Institute at Chicago
IC Faculty candidate
Abstact
In the traditional view of computation, a computational task is solved from scratch, and then remains solved forever. It is increasingly clear that this static model does not adequately capture the requirements of real-world computation. For instance, in a communication network, new links appear and disappear all the time. Recomputing everything from scratch (to obtain, for instance, connectivity-information about the network) is clearly wasteful. Similar dynamic scenarios arise in most modern applications, including load balancing in parallel computation, tracking communities in social networks, financial fraud detection, and routing.
Dynamic graph algorithms aim to address this issue; they maintain information about graphs that undergo edge/vertex updates without recomputing everything from scratch after each update.
These algorithms are promising for all the practical applications mentioned above and have deep theoretical applications. Unfortunately, even the most basic graph problems, such as graph connectivity and shortest paths, are still not well-understood in the dynamic setting.
In this talk, I will talk about two general techniques recently used to break decades-old barriers on many dynamic graph problems: 1) dynamic expander decomposition and 2) local clustering.
The new development of these techniques on dynamic graphs, in turn, leads to exciting applications even in the classical static setting. For example, they improve the 50-year-old quadratic time bound for checking k-vertex-connectivity to nearly linear time.
Bio
Thatchaphol Saranurak is a theoretical computer scientist, currently holding a research assistant professor position at Toyota Technological Institute at Chicago, USA.
He completed his Ph.D. at KTH Royal Institute of Technology in 2018 where he was supervised by Danupon Nanongkai.
His main research interest is on graph algorithms with a current focus on dynamic, local, and distributed algorithms.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Ola Svensson