Xiao Mao

Conference Papers

• Approximation schemes for Edit Distance and LCS in quasi-strongly subquadratic time
  Xiao Mao, Aviad Rubinstein
  ACM Symposium on Theory of Computing (STOC 2026)


• Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
  Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, Mirza Redžić
  ACM Symposium on Theory of Computing (STOC 2026)


• Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
  Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
  ACM Symposium on Theory of Computing (STOC 2025). Best Paper Award. Invited to the Journal of the ACM
  [arXiv]


• Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
  Xiao Mao
  ACM Symposium on Theory of Computing (STOC 2024)
  [arXiv]


• (1−ε)-Approximation of Knapsack in Nearly Quadratic Time
  Xiao Mao
  ACM Symposium on Theory of Computing (STOC 2024)
  [arXiv]


• Approximating Knapsack and Partition via Dense Subset Sums
  Mingyang Deng, Ce Jin, Xiao Mao
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
  [arXiv]


• On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
  Mingyang Deng, Xiao Mao, Ziqian Zhong
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
  [arXiv]


• Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
  Xiao Mao
  IEEE Symposium on Foundations of Computer Science (FOCS 2021). Machtey Award for Best Student Paper, sole winner. Invited to the SICOMP Special Issue for FOCS 2021
  [SIAM Journal Version] [arXiv]
  My first peer-reviewed publication