Tata Institute of Fundamental Research
Spectral Methods in Modern Graph Algorithms
STCS Seminar
Speaker:
Akash Kumar (EPFL, Lausanne, CH)
Organiser:
Umang Bhaskar
Date:
Tuesday, 8 Mar 2022, 16:00 to 17:00
Venue:
Via Zoom
(Scan to add to calendar)
Abstract:
Spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In my research so far, I have used spectral methods to develop algorithms for problems on planar graphs, and to develop algorithms to recover planted subgraphs in an otherwise gigantic random graph.
In this talk, I will focus on my contributions towards algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stoman, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called "efficient partition oracle" problem [K.-Seshadhri-Stolman, FOCS 2021].
Bio: Akash Kumar is a postdoc at EPFL (Switzerland). His research interests lie in spectral graph theory and property testing. Before starting his postdoctoral position, he completed his PhD from Purdue University (USA) in May 2020 under the supervision of Saugata Basu.
Join Zoom Meeting
https://zoom.us/j/99710687041?pwd=eHRvT1Y3OFJYMFk1QXNnVnFvMXZvUT09
Meeting ID: 997 1068 7041
Passcode: 543679
| Speaker: | Akash Kumar (EPFL, Lausanne, CH) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 8 Mar 2022, 16:00 to 17:00 |
| Venue: | Via Zoom |
(Scan to add to calendar)
Abstract:
Spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In my research so far, I have used spectral methods to develop algorithms for problems on planar graphs, and to develop algorithms to recover planted subgraphs in an otherwise gigantic random graph.
In this talk, I will focus on my contributions towards algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stoman, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called "efficient partition oracle" problem [K.-Seshadhri-Stolman, FOCS 2021].
Bio: Akash Kumar is a postdoc at EPFL (Switzerland). His research interests lie in spectral graph theory and property testing. Before starting his postdoctoral position, he completed his PhD from Purdue University (USA) in May 2020 under the supervision of Saugata Basu.
Join Zoom Meeting
https://zoom.us/j/99710687041?pwd=eHRvT1Y3OFJYMFk1QXNnVnFvMXZvUT09
Meeting ID: 997 1068 7041
Passcode: 543679
In this talk, I will focus on my contributions towards algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stoman, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called "efficient partition oracle" problem [K.-Seshadhri-Stolman, FOCS 2021].
Bio: Akash Kumar is a postdoc at EPFL (Switzerland). His research interests lie in spectral graph theory and property testing. Before starting his postdoctoral position, he completed his PhD from Purdue University (USA) in May 2020 under the supervision of Saugata Basu.
Join Zoom Meeting
https://zoom.us/j/99710687041?pwd=eHRvT1Y3OFJYMFk1QXNnVnFvMXZvUT09
Meeting ID: 997 1068 7041
Passcode: 543679