Recent Publications

In theoretical computer science, it is customary for the authors to be listed alphabetically. 

• A Little Clairvoyance Is All You Need  [PDF]
  Anupam Gupta, Haim Kaplan,  Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai
  FOCS'25

• Global vs. s-t Vertex Connectivity Beyond Sequential:  Almost-Perfect Reductions & Near-Optimal Separations  [PDF]
  Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
  STOC'25

• Deterministic Vertex Connectivity via Common-Neighborhood  Clustering and Pseudorandomness [PDF]
  Yonggang Jiang , Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
  STOC'25

• Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth  [PDF] [Slides]
  Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
  STOC'25

• Hardness Amplification for Dynamic Binary Search Trees [PDF]
  Shunhua Jiang, Victor Lecomte, Omri Weinstein, Sorrachai Yingchareonthawornchai
  ISAAC'24

• The Group Access Bounds for Binary Search Trees [PDF]
  Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, Sorrachai Yingchareonthawornchai
  ICALP'24

• An FPTAS for Connectivity Interdiction
  Chien-Chung Huang, Nidia Obscura Acosta, Sorrachai Yingchareonthawornchai
  IPCO'24

• Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns [PDF]
  Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
  SODA'24

• Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition [PDF]
  Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai
  SODA'23

• Deterministic Small Vertex Connectivity in Almost Linear Time [PDF][Video]
  Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
  FOCS'22

• Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver [PDF] [Video]
  Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
  ICALP'22

• Vertex Connectivity in Poly-Logarithmic Max-Flows  [PDF] [Video]
  Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
  STOC'21,  JACM'25

• Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity [PDF]  [Source Code]
  Max Franck, Sorrachai Yingchareonthawornchai
  SEA'21, ACM Journal of Experimental Algorithmics'22

• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms   [PDF] [Slides by SF]
  Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
  SODA'20

• Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme [PDF] [Video by TS]
  Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
  STOC'19

Masters Students Supervised with Theses at Aalto University

• Max Flanck,  January 2021, An Experimental Study of a Near-Linear Time Algorithm for Small Vertex Connectivity.

• Natalia Kushnerchuk,  August 2023,  Problems around the Stanley-Wilf Limits of Permutation. 

Academic Services

• Organizer: Aalto TCS theory seminar, Spring 2023 . 

• Reviewer: IEEE Transaction on Networking (TON) (2021)

• Program Committee: ESA 2025, (Upcoming) ICALP 2026, COCOON 2026 

• Conference Subreviewers:  ICALP 2019, DISC 2019, SOSA 2020, SWAT 2020, SODA 2021, SOSA 2021, ICALP 2021, FOCS 2022, SODA 2023, SOSA 2023, ITCS 2023, STOC 2023, FOCS 2023, SODA 2024, ITCS 2024, ISAAC 2024,  STOC 2024,  FOCS 2024, SODA 2025, STOC 2025, FOCS 2025, SODA 2026. 

Formalized Mathematics:

• (WIP) Formalizing Forbidden 0-1 Matrix Theory in Lean 4 

• (WIP) Formalizing Greedy Spanner Algorithms in Lean 4