Research

Derandomizing matrix concentration inequalities from free probability [pdf]
Robert Wang, Lap Chi Lau, Hong Zhou
Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), 2026. [pdf]

A combinatorial characterization of constant mixing time [pdf]
Lap Chi Lau, Raymond Liu
Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS), 92:1-92:13, 2026. [pdf]

Optimal bounds for Tyler's M-estimator for elliptical distributions [pdf]
Akshay Ramachandran, Lap Chi Lau
Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT), 2026.
"Elegant Paper Badge"

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

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

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. [pdf]

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. [pdf]

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
SIAM Journal on Computing, 54(6), 1568-1625, 2025.
(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

	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.