Information for


Lap Chi LauResearch interests

Lap Chi’s research interests are in algorithmic graph theory, approximation algorithms and combinatorial optimization. He is always interested in studying different approaches to solve graph problems and seeing new connections between them. He has made contributions in designing good approximation algorithms and also fast exact algorithms for graph problems, using ideas from linear algebra, probability and combinatorial optimization. Recently, he has been working on spectral graph theory to tackle fundamental combinatorial problems.

Degrees and awards

PhD (Toronto), MSc (Toronto), BSc (CUHK)

Doctoral prize from the Natural Science and Engineering Research Council of Canada, 2008.

Doctoral prize from the Canadian Mathematical Society, 2007.

Machtey award for best student paper at the IEEE Conference on Foundations of Computer Science (FOCS), 2004.

Microsoft graduate research fellowship, 2005-2007.

Industrial and sabbatical experience

Simons Institute and University of California, Berkeley, 2014-2015.

Microsoft Research, New England, 2009.

Representative publications

T.C. Kwok, L.C. Lau, Y.T. Lee, S. Oveis Gharan, L. Trevisan.  Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.  Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 11-20, 2013.

H.Y. Cheung, T.C. Kwok, L.C. Lau.  Fast matrix rank algorithms and applications.  Journal of the ACM, 60(5), #31, 2013.

H.Y. Cheung, L.C. Lau, K.M. Leung.  Graph connectivities, network coding, and expander graphs.  SIAM Journal on Computing, 42(3), 733-751, 2013.

L.C. Lau, R. Ravi, M. Singh.  Iterative Methods in Combinatorial Optimization.  Cambridge University Press, 2011.

L.C. Lau. An approximate max-Steiner-tree-packing min-Steiner-cut theorem.  Combinatorica, 27(1), 71-90, 2007.

University of Waterloo
Contact information: