Thesis Information
Title: Dynamic algorithms: new worst-case and instance-optimal bounds via new connections
Adviser: Danupon Nanongkai
Institution: KTH Royal Institute of Technology
Graduation Date: September 2018
Contact Information
Email Candidate
Candidate Website
SIGACT Membership No.: 1921369
Candidate Bio:
Thatchaphol Saranurak is a research assistant professor at Toyota Technological Institute at Chicago. His main research interest is efficient graph algorithms, in particular for dynamic and distributed models. Thatchaphol completed his PhD at KTH Royal Institute of Technology in 2018 where he was supervised by Danupon Nanongkai. His dissertation focused on showing new connections between dynamic data structures and to other areas, including approximation algorithms, local algorithms, streaming algorithms, fine-grained complexity theory, and combinatorics.
Paper 1:
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time, Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen, FOCS 2019
Link to PDFPaper 2:
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme, Danupon Nanongkai, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai, STOC 2019 (special isssue)
Link to PDFPaper 3:
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond, Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng and Thatchaphol Saranurak, 2019
Link to PDFKeywords: Algorithms and data structures, parallel and distributed algorithms, algorithmic graph theory and combinatorics