Siu On Chan

About me

I am a PhD student in theoretical computer science at Berkeley. My advisors are Luca Trevisan and Elchanan Mossel. I did my undergrad at Chinese University of Hong Kong, under Leizhen Cai, and my masters at University of Toronto, under Mike Molloy.

My brother is also interested in complexity theory.

Research interests

Inapproximability, Distributional property testing, Random graphs

Teaching assistant

• CS 61B (Data structures), CS 70 (Discrete Math), CS 170 (Algorithms)

Research

• Efficient Density Estimation via Piecewise Polynomial Approximation
  with Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun
  arXiv 2013 [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. The journal version will have an improved presentation.
• Learning Mixtures of Structured Distributions over Discrete Domains
  with Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun
  SODA 2013
• On Extracting Common Random Bits from Correlated Sources on Large Alphabets
  with Joe Neeman and Elchanan Mossel
  arXiv 2012 [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]