Loading Events

« All Events

  • This event has passed.

Akash Kumar, Random walks and Forbidden Minors

Wednesday, August 10, 2022 @ 4:30 PM - 5:30 PM KST

Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]


Akash Kumar
École Polytechnique Fédérale de Lausanne (EPFL)

Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how random walks helped make progress on 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-Stolman, 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.


Wednesday, August 10, 2022
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]


Joonkyung Lee (이준경)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.