Xiaorui Sun

Email: xiaorui at uic dot edu

I am an assistant professor in the Computer Science Department of University of Illinois at Chicago, where I am part of the Theory Group.

Prior to joining UIC, I was at UC Berkeley Simons Institute and Microsoft Research. I recieved my PhD in 2016 from Columbia University, where I was fortunate to be advised by Xi Chen. I recieved my MS and BE from Shanghai Jiao Tong University.

My research is in theoretical computer science. More specifically, I work in parallel algorithms, sublinear algorithms and graph algorithms.

Teaching

Fall 2018, Fall 2019, Fall 2020: CS 401 Computer Algorithms I

Spring 2019, Spring 2020: CS 594 Algorithm Methods for Big Data

Papers

On the Hardness of Massively Parallel Computation [arxiv]
Kai-Min Chung, Kuan-Yi Ho, Xiaorui Sun
SPAA 2020
Fast Noise Removal for k-Means Clustering [arxiv]
Sungjin Im, Mahshid Montazer Qaem, Benjamin Moseley, Xiaorui Sun, Rudy Zhou
AISTATS 2020
Parallel Batched-Dynamic Graph Algorithms in Constant Rounds [arxiv]
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 Algorithms for Finding Well-Connected Components in Sparse Graphs [arxiv]
Sepehr Assadi, Xiaorui Sun, Omri Weinstein
PODC 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
Probability-Revealing Samples
Krzysztof Onak, Xiaorui Sun
AISTATS 2018
Linear Regression Without Correspondence
Daniel Hsu, Kevin Shi, Xiaorui Sun
NIPS 2017
Correspondence retrieval
Alexandr Andoni, Daniel Hsu, Kevin Shi, Xiaorui Sun
COLT 2017
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
Optimal Pricing in Social Networks with Incomplete Information [arxiv]
Wei Chen, Pinyan Lu, Bo Tang, Xiaorui Sun, Yajun Wang, Zeyuan Allen Zhu
WINE 2011
Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games[pdf]
Pinyan Lu, Xiaorui Sun, Yajun Wang, Zeyuan Allen Zhu
EC 2010
A Game Theoretic Framework to Identify Overlapping Communities in Social Network [pdf]
Wei Chen, Zhenming Liu, Xiaorui Sun, Yajun Wang
ECMLPKDD 2010
Best Student Paper
Invited to Data Mining and Knowledge Discovery Journal and IJCAI 2011
The Key-Dependent Attack on Block Ciphers
Xuejia Lai, Xiaorui Sun
Asiacrypt 2009
Improved Integral Attack on MISTY1
Xuejia Lai, Xiaorui Sun
SAC 2009