Lap Chi Lau | Research
. home . about . research . teaching .
 Book & Thesis
Iterative Methods in Combinatorial Optimization [pdf]
Lap Chi Lau, R. Ravi, Mohit Singh
Cambridge University Press, 2011

On approximate min-max theorems for graph connectivity problems [ps] [pdf]
University of Toronto, 2006

Doctoral Prize 2008 from Natural Sciences and Engineering Research Council of Canada.
Doctoral Prize 2007 from the Canadian Mathematical Soceity.
 Combinatorial Optimization, Approximation Algorithms
Random walks and evolving sets: faster convergences and limitations [pdf]
Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau
(Conference version in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1849-1865, 2017. [pdf])
Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile [pdf]
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee
(Conference version in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1848-1861, 2016. [pdf])
Lower bounds on expansions of graph powers [pdf]
Tsz Chiu Kwok, Lap Chi Lau
Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 313-324, 2014
A unified algorithm for degree bounded survivable network design [pdf]
Lap Chi Lau, Hong Zhou
Mathematical Programming, 154(1-2), 515-532, 2015.
(Conference version in Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 369-380, 2014 [pdf])
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap [ps] [pdf]
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
(Conference version in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 11-20, 2013 [pdf])
Finding small sparse cuts by random walk [ps] [pdf]
Tsz Chiu Kwok, Lap Chi Lau
Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM), 615-626, 2012
Fast matrix rank algorithms and applications [pdf]
Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
Journal of the ACM, 60(5), #31, 2013
(Conference version in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 549-562, 2012 [ps] [pdf])
Graph connectivities, network coding, and expander graphs [pdf]
Ho Yee Cheung, Lap Chi Lau, Kai Man Leung
SIAM Journal on Computing, 42(3), 733-751, 2013
(Conference version in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 190-199, 2011 [ps] [pdf])
On disjoint common bases in two matroids [ps] [pdf]
Nick Harvey, Tamás Király, Lap Chi Lau
SIAM Journal on Discrete Mathematics, 25(4), 1792-1803, 2011
Degree bounded forest covering [ps] [pdf]
Tamás Király, Lap Chi Lau
Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 315-323, 2011
Algebraic algorithms for linear matroid parity problems [pdf]
Ho Yee Cheung, Lap Chi Lau, Kai Man Leung
ACM Transactions on Algorithms, 10(3), #10, 2014
(Conference version in Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1366-1382, 2011 [ps] [pdf])
Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities [pdf]
Lap Chi Lau, Chun Kong Yung
SIAM Journal on Computing, 42(3), 1185-1200, 2013
(Conference version in Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 96-109, 2010 [ps] [pdf])
On linear and semidefinite programming relaxations for hypergraph matching [pdf]
Yuk Hei Chan, Lap Chi Lau
Mathematical Programming 135(1-2), 123-148, 2012
(Conference version in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1500-1511, 2010 [ps] [pdf])
Degree bounded network design with metric costs [pdf]
Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung
SIAM Journal on Computing, 40(4), 953-980, 2011
(Conference version in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 125-134, 2008 [ps] [pdf])
Additive approximation for bounded degree survivable network design [pdf]
Lap Chi Lau, Mohit Singh
SIAM Journal on Computing, 42(6), 2217-2242, 2013
(Conference version in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 759-768, 2008 [ps] [pdf])
Degree bounded matroids and submodular flows [pdf]
Tamás Király, Lap Chi Lau, Mohit Singh
Combinatorica, 32(6), 703-720, 2012
(Conference version in Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 259-272, 2008 [ps] [pdf])
Approximating minimum bounded degree spanning tress to within one of optimal [pdf]
Mohit Singh, Lap Chi Lau
Journal of the ACM, 62(1), #1, 2015.
(Conference version in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 661-670, 2007 [ps] [pdf])
Survivable network design with degree or order constraints [pdf]
Lap Chi Lau, Joseph Naor, Mohammad Salavatipour, Mohit Singh
SIAM Journal on Computing, 39(3), 1062-1087, 2009
(Conference version in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 651-660, 2007 [ps] [pdf])
Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs [pdf]
Tamás Király, Lap Chi Lau
Journal of Combinatorial Theory, Series B, 98(6), 1233-1252, 2008
(Conference version appeared in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 283-292, 2006 [ps] [pdf])
Packing Steiner forests [ps] [pdf]
Lap Chi Lau
Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 362-376, 2005
An approximate max-Steiner-tree-packing min-Steiner-cut theorem [pdf]
Lap Chi Lau
Combinatorica, 27(1), 71-90, 2007
(Conference version appeared in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 61-70, 2004 [ps] [pdf])

Machtey Award for best student paper
 Graph Algorithms
Complexity of finding graph roots with girth conditions [pdf]
Babak Farzad, Lap Chi Lau, Van Bang Le, Ngoc Tuy Nguyen
Algorithmica, 62, 38-53, 2012.
(Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), 397-408, 2009 [pdf])
A note on degree specified subgraphs [ps] [pdf]
András Frank, Lap Chi Lau, Jácint Szabó
Discrete Mathematics, 308, 2647-2648, 2008
Randomly colouring graphs with girth five and large maximum degree [ps] [pdf]
Lap Chi Lau, Michael Molloy
Proceedings of the 7th Latin American Symposium of Theoretical Informatics (LATIN), 656-676, 2006
Bipartite roots of graphs [pdf]
Lap Chi Lau
ACM Transactions on Algorithms, 2(2), 178-208, 2006
(Conference version in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 952-961, 2004 [ps] [pdf])
Recognizing powers of proper interval, split, and chordal graphs [ps] [pdf]
Lap Chi Lau, Derek Corneil
SIAM Journal on Discrete Mathematics, 18(1), 83-102, 2004
 Computer Networks
A constant bound on throughput improvement of multicast network coding in undirected networks [pdf]
Zongpeng Li, Baochun Li, Lap Chi Lau
IEEE Transactions on Information Theory, 55(3), 1016-1026, 2009
Conservative network coding [ps] [pdf]
Nick Harvey, Kamal Jain, Lap Chi Lau, Chandra Nair, Yunnan Wu
Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing (Allerton), 2006
On achieving maximum multicast throughput in undirected networks [ps] [pdf]
Zongpeng Li, Baochun Li, Lap Chi Lau
IEEE Transactions on Information Theory, 52(6), 2467-2485, 2006
(Conference version in 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2184-2194, 2005 [ps] [pdf])