Siu On Chan

36 papers A* 12B 1Journal 19Unranked 3
YearRankTypeTitle / Venue / Authors
2025 A* conf
How Random CSPs Fool Hierarchies: II.
STOC
Siu On Chan, Hiu Tsun Ng
2025 J jnl
How Random CSPs Fool Hierarchies: II.
Electron. Colloquium Comput. Complex.
Siu On Chan, Hiu Tsun Ng
2024 A* conf
How Random CSPs Fool Hierarchies.
STOC
Siu On Chan, Hiu Tsun Ng, Sijin Peng
2024 J jnl
How Random CSPs Fool Hierarchies.
Electron. Colloquium Comput. Complex.
Siu On Chan, Hiu Tsun Ng, Sijin Peng
2022 J jnl
Rethinking Graph Neural Networks for the Graph Coloring Problem.
CoRR
Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Z. Pan, Bei Yu
2021 B conf
Learning and Testing Irreducible Markov Chains via the k-Cover Time.
ALT
Siu On Chan, Qinghua Ding, Sing Hei Li
2020 A* conf
The Gambler's Problem and Beyond.
ICLR
Baoxiang Wang, Shuai Li, Jiajin Li, Siu On Chan
2020 J jnl
The Gambler's Problem and Beyond.
CoRR
Baoxiang Wang, Shuai Li, Jiajin Li, Siu On Chan
2017 A* conf
Random Walks and Evolving Sets: Faster Convergences and Limitations.
SODA
Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau
2016 J jnl
Approximate Constraint Satisfaction Requires Large LP Relaxations.
J. ACM
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2016 J jnl
Approximation Resistance from Pairwise-Independent Subgroups.
J. ACM
Siu On Chan
2016 A* conf
On the Approximability of Sparse PCA.
COLT
Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein
2015 J jnl
On the Worst-Case Approximability of Sparse PCA.
CoRR
Siu On Chan, Dimitris S. Papailiopoulos, Aviad Rubinstein
2015 J jnl
Random Walks and Evolving Sets: Faster Convergences and Limitations.
CoRR
Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau
2015 A* conf
Sum of Squares Lower Bounds from Pairwise Independence.
STOC
Boaz Barak, Siu On Chan, Pravesh K. Kothari
2015 J jnl
Sum of Squares Lower Bounds from Pairwise Independence.
CoRR
Boaz Barak, Siu On Chan, Pravesh Kothari
2014 A* conf
Efficient density estimation via piecewise polynomial approximation.
STOC
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014 — conf
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.
NIPS
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014 J jnl
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.
CoRR
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014 J jnl
On Extracting Common Random Bits From Correlated Sources on Large Alphabets.
IEEE Trans. Inf. Theory
Siu On Chan, Elchanan Mossel, Joe Neeman
2014 A* conf
Optimal Algorithms for Testing Closeness of Discrete Distributions.
SODA
Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant
2013 J jnl
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems.
SIAM J. Comput.
Siu On Chan, Michael Molloy
2013 A* conf
Approximate Constraint Satisfaction Requires Large LP Relaxations.
FOCS
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013 J jnl
Approximate Constraint Satisfaction Requires Large LP Relaxations.
CoRR
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013 A* conf
Approximation resistance from pairwise independent subgroups.
STOC
Siu On Chan
2013 J jnl
Efficient Density Estimation via Piecewise Polynomial Approximation
CoRR
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2013 — —
Hardness of Maximum Constraint Satisfaction.
Siu On Chan
2013 A* conf
Learning mixtures of structured distributions over discrete domains.
SODA
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2013 J jnl
Optimal Algorithms for Testing Closeness of Discrete Distributions.
CoRR
Siu On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant
2012 J jnl
(
Comb. Probab. Comput.
Siu On Chan, Michael Molloy
2012 J jnl
Approximation Resistance from Pairwise Independent Subgroups.
Electron. Colloquium Comput. Complex.
Siu On Chan
2012 J jnl
Learning mixtures of structured distributions over discrete domains
CoRR
Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2012 J jnl
On extracting common random bits from correlated sources on large alphabets
CoRR
Siu On Chan, Elchanan Mossel, Joe Neeman
2011 — conf
Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.
FSTTCS
Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen
2008 A* conf
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems.
FOCS
Siu On Chan, Michael Molloy
2006 — conf
Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems.
IWPEC
Leizhen Cai, Siu Man Chan, Siu On Chan