University of Waterloo COVID-19 update

The University of Waterloo is constantly updating its most frequently asked questions.

Questions about buildings and services? Please visit the list of modified services.

Please note: The University of Waterloo is closed for all events until further notice.

Lap Chi Lau


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: 

Profiles by type