Xiaorui Sun
Assistant Professor
Department of Computer Science
Contact
Building & Room:
1241 SEO
Address:
851 S. Morgan St, MC 152, Chicago, IL, 60607
Office Phone:
Email:
Related Sites:
About
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 Im, Benjamin 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 Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
FOCS 2015 - Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms[nips]
Siu On Chan, Ilias Diakonikolas, Rocco Servedio, Xiaorui Sun
NIPS 2014 - Efficient Density Estimation via Piecewise Polynomial Approximation [arxiv]
Siu On Chan, Ilias Diakonikolas, Rocco 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 Tan, John Wright, Yu Zhao
CCC 2014 - The Complexity of Optimal Multidimensional Pricing [arxiv]
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
SODA 2014 - Faster Canonical Forms For Strongly Regular Graphs [pdf]
László Babai, Xi 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 Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
SODA 2013 - Information Dissemination via Random Walks in d-Dimensional Space [arxiv]
Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, Yajun Wang
SODA 2012
Education
Ph.D., Computer Science, Columbia University, NY