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.
