Siu On Chan
Assistant Professor, CSE, CUHK
Before joining The Chinese University of Hong Kong, I was a postdoc researcher at Microsoft Research New England. Before that, I got a PhD in theoretical computer science at UC Berkeley. My advisors were Luca Trevisan and Elchanan Mossel. Earlier, I did my masters at University of Toronto, under Michael Molloy, and my undergrad at The Chinese University of Hong Kong, working with Leizhen Cai.
I am interested in understanding the limitations of approximation algorithms, especially convex optimization algorithms. I am also interested in random graphs, testing and learning.
Rm 911, Ho Sin Hang Engineering Building (…)
siuoncse.cuhk.edu.hk
(+852) 3943 4263
Teaching
- CSCI3130: Formal Languages and Automata Theory
Fall 2021, Fall 2020, Fall 2019, Fall 2018, Fall 2017, Fall 2016, Fall 2015 - CSCI4230: Computational Learning Theory
Spring 2021, Spring 2019 - CSCI5160: Approximation Algorithms
Spring 2021, Spring 2020, Spring 2018, Spring 2017 - CSCI3270: Advanced Programming Laboratory
Fall 2018
Services
Program committees: FOCS 2019, SODA 2019, APPROX 2017, FOCS 2016, APPROX 2015Publications
- Learning and Testing Irreducible Markov Chains via the k-Cover Time
with Qinghua Ding, and Singhei Li
ALT 2021 - The Gambler's Problem and Beyond
Baoxiang Wang, Shuai Li, Jiajin Li, Siu On Chan
ICLR 2020; arXiv [pdf] - Random Walks and Evolving Sets: Faster Convergences and Limitations
with Tsz Chiu Kwok, and Lap Chi Lau
SODA 2017; arXiv [pdf] Talk [pdf] - Quantifying the Unobserved Protein-Coding Variants in Human Populations Provides a Roadmap for Large-Scale Sequencing Projects
James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Exome Aggregation Consortium, Shamil Sunyaev, Mark Daly, Daniel MacArthur
To appear in Nature Communications; bioRxiv [pdf] - On the Approximability of Sparse PCA
with Dimitris Papailliopoulos, and Aviad Rubinstein
COLT 2016; arXiv [pdf] - Sum of Squares Lower Bounds from Pairwise
Independence
with Boaz Barak, and Pravesh Kothari
STOC 2015; arXiv [pdf] - Near-Optimal Density Estimation in Near-Linear
Time Using Variable-Width Histograms
with Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun
NIPS 2014 [pdf] - Efficient Density Estimation via Piecewise
Polynomial Approximation
with Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun
STOC 2014; arXiv [pdf] - Optimal Algorithms for Testing Closeness of
Discrete Distributions
with Ilias Diakonikolas, Gregory Valiant and Paul Valiant
SODA 2014; arXiv [pdf] - Approximate Constraint Satisfaction Requires
Large LP Relaxations
with James R. Lee, Prasad Raghavendra, and David Steurer
FOCS 2013, invited to special issue but regretfully declined
arXiv [pdf] and JACM [pdf] - Approximation Resistance from Pairwise
Independent Subgroups
STOC 2013, co-winner of Best Paper Award and Best Student Paper Award. ECCC [pdf] Talk [pdf]
Invited to JACM [pdf]. The journal version has a better presentation - Learning Mixtures of Structured Distributions
over Discrete Domains
with Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun
SODA 2013 [pdf] - On Extracting Common Random Bits from
Correlated Sources on Large Alphabets
with Joe Neeman and Elchanan Mossel
IEEE Transactions on Information Theory 2014; arXiv [pdf] - Tight Integrality Gap for Sherali–Adams
SDPs for Vertex Cover
with Siavosh Benabbas, Konstantinos Georgiou, and Avner Magen
FSTTCS 2011 [pdf] - (k+1)-Cores Have k-Factors
with Mike Molloy
CPC 2012 [pdf] - A PSD Lifting Question of Lee
Manuscript 2011; Last updated Nov 2012 [pdf] - A Dichotomy Theorem for the Resolution
Complexity of Random Constraint Satisfaction Problems
with Mike Molloy
FOCS 2008 [pdf] SICOMP 2013 [pdf] - Random Separation: A New Method for Solving
Fixed-Cardinality Optimization Problems
with Leizhen Cai and Siu Man Chan
IWPEC 2006 [pdf]