Date and Time: Wednesday, 16th Feb 2022, 9pm (Online)
Spectral Methods in Modern Graph Algorithms
Akash Kumar
EPFL, Switzerland.
16-02-22

---

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].

The talk will assume minimal background by presenting a stand-alone story that should be of interest to students/researchers in computer science.

About the Speaker: Akash Kumar is currently 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.