. 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.

  Spectral Graph Theory

Spectral sparsification by deterministic discrepancy walks [pdf] Lap Chi Lau, Robert Wang, Hong Zhou Proceedings of the 8th Symposium on Simplicity in Algorithms (SOSA), 2025.

Experimental design using interlacing polynomials [pdf] Lap Chi Lau, Robert Wang, Hong Zhou Proceedings of the 8th Symposium on Simplicity in Algorithms (SOSA), 2025.

Fast algorithms for directed graph partitioning using flows and reweighted eigenvalues [pdf] Lap Chi Lau, Kam Chuen Tung, Robert Wang Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), 591-624, 2024. [pdf]

On the Houdré-Tetali conjecture about an isoperimetric constant of graphs [pdf] Lap Chi Lau, Dante Tjowasi Proceedings of the 28th International Conference on Randomization and Computation (RANDOM), 36:1-18, 2024.

Experimental design for any p-norm [pdf] Lap Chi Lau, Robert Wang, Hong Zhou Proceedings of the 26th International Conference on Approximation Algorithms for Combinatorial Optimization (APPROX), 4:1-21, 2023.

Cheeger inequalities for directed graphs and hypergraphs using reweighted eigenvalues [pdf] Lap Chi Lau, Kam Chuen Tung, Robert Wang (Conference version in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), 2023. [pdf])

Cheeger inequalities for vertex expansion and reweighted eigenvalues [pdf] Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung (Conference version in Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 366-377, 2022. [pdf])

A local search framework for experimental design [pdf] Lap Chi Lau, Hong Zhou SIAM Journal on Computing, 51(4), 900-951, 2022. (Conference version in Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 1039-1058, 2021. [pdf])

A spectral approach to network design [pdf] Lap Chi Lau, Hong Zhou SIAM Journal on Computing, 51(4), 1018-1064, 2022. (Conference version in Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), 826-839, 2020. [pdf])

Improved analysis of higher order random walks and applications [pdf] Vedat Levi Alev, Lap Chi Lau Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), 1198-1211, 2020. [pdf]

Spectral analysis of matrix scaling and operator scaling [pdf] Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran SIAM Journal on Computing, 50(3), 1034-1102, 2021. (Conference version in Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1184-1204, 2019. [pdf])

Network design for s-t effective resistance [pdf] Pak Hay Chan, Lap Chi Lau, Aaron Schild, Sam Chiu-wai Wong, Hong Zhou ACM Transactions on Algorithms, 18(3), 22:1-45, 2022.

The Paulsen problem, continuous operator scaling, and smoothed analysis [pdf] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran (Conference version in Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 182-189, 2018. [pdf])

Graph clustering using effective resistance [pdf] Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS), 41:1-41:16, 2018. [pdf]

Random walks and evolving sets: faster convergences and limitations [pdf] Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau 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 SIAM Journal on Computing, 46(3), 890-910, 2017. (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

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

 Combinatorial Optimization, Approximation Algorithms

Streaming and communication complexity of load balancing via matching contractors [pdf] Sepehr Assadi, Aaron Bernstein, Zachary Langley, Lap Chi Lau, Robert Wang Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. [pdf]

Approximating unique games using low diameter graph decomposition [pdf] Vedat Levi Alev, Lap Chi Lau (Conference version in Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 18:1-18:15, 2017 [pdf])

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])

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])

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])

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

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])