Chris Liaw

About Me

I am a PhD student at the Department of Computer Science at UBC. My advisor is Nick Harvey. I am broadly interested in randomized algorithms, machine learning theory, and mechanism design.


Publications (in a noisy chronological order)

  1. Nearly-tight sample complexity bounds for learning mixtures of Gaussians via compression schemes (with Hassan Ashtiani, Shai Ben-David, Nick Harvey, Abbas Mehrabian, and Yaniv Plan)
    in NeurIPS 2018 (best paper) [ arXiv ]

  2. Greedy and local ratio algorithms in the MapReduce model (with Nick Harvey and Paul Liu)
    in SPAA 2018 [ arXiv ]

  3. Approximation schemes for covering and packing in the streaming model (with Paul Liu and Robert Reiss)
    in CCCG 2018 [ arXiv, slides ]

  4. The value of information concealment (with Hu Fu, Pinyan Lu, and Zhihao Tang)
    in SODA 2018 [ arXiv ]

  5. Nearly-tight VC-dimension bounds for piecewise linear neural networks (with Peter L. Bartlett, Nick Harvey, and Abbas Mehrabian)
    in COLT 2017 [ extended abstract, arXiv, slides ]

  6. Tight load balancing via randomized local search (with Petra Berenbrink, Peter Kling, and Abbas Mehrabian)
    in IPDPS 2017 [ arXiv ]

  7. A simple tool for bounding the deviation of random matrices on geometric sets (with Abbas Mehrabian, Yaniv Plan, and Roman Vershynin)
    in Geometric Aspects of Functional Analysis [ arXiv ]

  8. Rainbow Hamilton cycles and lopsidependency (with Nick Harvey)
    in Discrete Mathematics [ pdf ]