Your browser is unsupported

We recommend using the latest version of IE11, Edge, Chrome, Firefox or Safari.

Photo of Sun, Xiaorui

Xiaorui Sun

Assistant Professor

Department of Computer Science


Building & Room:

1241 SEO


851 S. Morgan St, MC 152, Chicago, IL, 60607

Office Phone:


Related Sites:


I am an assistant professor in the Computer Science Department of University of Illinois at Chicago.

Prior to joining UIC, I was at UC Berkeley Simons Institute and Microsoft Research. I received my Ph.D. in 2016 from Columbia University, where I was fortunate to be advised by Xi Chen.

Research Interests:

Design and analysis of algorithms, including graph algorithms, parallel algorithms, dynamic algorithms, and distributed algorithms.

Selected Publications

  • Parallel Batched-Dynamic Graph Algorithms in Constant Rounds
    David Durfee, Janardhan Kulkarni, Laxman Dhulipala, Richard Peng, Saurabh Sawlani, Xiaorui Sun
    SODA 2020
  • Approximation Algorithms for LCS and LIS with Truly Improved Running Times
    Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
    FOCS 2019
  • Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence [link]
    MohammadTaghi Hajiaghayi, Saeed Seddighin, Xiaorui Sun
    SODA 2019
  • Approximating LCS in Linear Time: Beating the Barrier [link]
    MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiaorui Sun
    SODA 2019
  • The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
    Krzysztof Onak, Xiaorui Sun
    STOC 2018
  • Efficient Massively Parallel Methods for Dynamic Programming
    Sungjin ImBenjamin Moseley, Xiaorui Sun
    STOC 2017
  • Faster Canonical Forms for Primitive Coherent Configurations [arxiv]
    Xiaorui Sun, John Wilmes
    STOC 2015
    Invited to the SIAM Journal on Computing Special Issue
  • On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
    Xi ChenIlias DiakonikolasAnthi OrfanouDimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
    FOCS 2015
  • Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms[nips]
    Siu On Chan, Ilias DiakonikolasRocco Servedio, Xiaorui Sun
    NIPS 2014
  • Efficient Density Estimation via Piecewise Polynomial Approximation [arxiv]
    Siu On Chan, Ilias DiakonikolasRocco Servedio, Xiaorui Sun
    STOC 2014
    Blog post about this work: MIT theory student blog 
  • A Composition Theorem for Parity Kill Number [arxiv]
    Ryan O’Donnell, Xiaorui Sun, Li-Yang TanJohn Wright, Yu Zhao
    CCC 2014
  • The Complexity of Optimal Multidimensional Pricing [arxiv]
    Xi ChenIlias DiakonikolasDimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
    SODA 2014
  • Faster Canonical Forms For Strongly Regular Graphs [pdf]
    László BabaiXi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
    FOCS 2013
    Invited to the SIAM Journal on Computing Special Issue
  • Multi-Stage Propagation and Quasipolynomial-Time Isomorphism Testing of Steiner 2-System
    Xi Chen, Xiaorui Sun, Shang-Hua Teng
    STOC 2013
  • Learning Mixtures of Structured Distributions over Discrete Domains [arxiv]
    Siu On ChanIlias DiakonikolasRocco A. Servedio, Xiaorui Sun
    SODA 2013
  • Information Dissemination via Random Walks in d-Dimensional Space [arxiv]
    Henry LamZhenming LiuMichael Mitzenmacher, Xiaorui Sun, Yajun Wang
    SODA 2012


Ph.D., Computer Science, Columbia University, NY