Cheriton School of Computer Science Professor Lap Chi Lau has been appointed a University Research Chair to recognize his many fundamental contributions to theoretical computer science. His research is in the field of algorithm design and analysis, with a focus on algorithms for graph theoretic problems.
University Research Chairs are a prestigious title held for up to seven years and are conferred both to recognize the exceptional achievements of Waterloo faculty members and to acknowledge their pre-eminence in a field of knowledge. The university makes at most five such appointments each year.
“Congratulations to Lap Chi on receiving this significant and much-deserved scholarly recognition,” said Raouf Boutaba, Professor and Director of the Cheriton School of Computer Science. “He is an outstanding computer scientist with a strong publication record in algorithm design and analysis, research that has been published in the top journals and presented at leading conferences in his field.”
“I feel very fortunate to be selected as there are many great researchers in the School and in the Faculty,” said Professor Lau. “I would like to thank the School and my colleagues, especially in the Algorithms and Complexity Group, who have been very supportive to me since I joined. This is a good opportunity to explore new research areas.”
Professor Lau is the tenth faculty member at the Cheriton School of Computer Science to be appointed a University Research Chair. Other faculty members are Professors Bin Ma (2021, 2008), Shai Ben-David (2020), Kate Larson (2019), Raouf Boutaba (2018), Lila Kari (2015), Ian Goldberg (2012), Timothy Chan (2005), Doug Stinson (2005), and Tamer Özsu (2004).
About Professor Lau and his research
Professor Lau graduated with a PhD from the University of Toronto. He was a faculty member in the Department of Computer Science and Engineering of the Chinese University of Hong Kong. He joined the Cheriton School of Computer Science as an Associate Professor in 2015 and became a Full Professor in 2021.
Professor Lau was a 2016 recipient of a CS-Can | Info-Can Outstanding Young Computer Science Researcher Award, a recognition of the leading young computer scientists in the nation. Within the Cheriton School of Computer Science, he was awarded a three-year Cheriton Faculty Fellowship in 2019 for research excellence, and a University of Waterloo Outstanding Performance Award in 2018 for his exceptional contributions in teaching and scholarship.
Professor Lau’s early work on the Steiner tree packing problem led to major progress in the field. He designed the first constant factor approximation algorithm for this problem, using combinatorial methods about matroids and submodular functions, a result of great interest to graph theorists. The work received the prestigious Machtey Award, which is conferred at the annual IEEE Symposium on Foundations of Computer Science to the author of the best student paper. For this research, Professor Lau was awarded both the Doctoral Prize from the Canadian Mathematical Society in 2007 and the Doctoral Prize from NSERC in 2008.
Since joining the Cheriton School of Computer Science, Professor Lau with his students has made progress on several problems related to spectral graph theory. Among them is Paulsen’s problem in frame theory — named after Waterloo Pure Mathematics Professor Vern Paulsen — that was solved by Professor Lau together with his doctoral student Akshay Ramachandran, his postdoc Tsz Chiu Kwok and his colleague Yin Tat Lee. For this work, Akshay received second place in the 2022 Mathematics Doctoral Prize as well as the 2022 Cheriton Distinguished Dissertation Award.
Professor Lau and his doctoral student Hong Zhou discovered that recent techniques in spectral sparsification can be used to design approximation algorithms for network design and showed that this spectral approach significantly extends the scope of network design problems that can be solved. Experimental design is a classical area in statistics that is also useful in machine learning. Using the new spectral approach, Professor Lau and Hong provided a unifying local search framework to match and improve all known results in experimental design and obtain new results in previously unknown settings. For this work, Hong received the 2021 Cheriton Distinguished Dissertation Award.
Professor Lau and his doctoral student Vedat Alev have proven a sharp eigenvalue bound about random walks in high dimensional expanders, which is important in the new spectral independence framework that leads to many recent breakthroughs in analyzing Markov chains.
Recently, Professor Lau and his doctoral students Alex Tung and Robert Wang are working to extend the fundamental results in spectral graph theory for undirected graphs to directed graphs and hypergraphs. This leads to a solution to the fastest mixing time problem for directed graphs.
Professor Lau has published 25 refereed journal articles and 33 refereed conference proceedings papers, many in the top journals and conferences in his field. With R. Ravi and Mohit Singh, he co-authored Iterative Methods in Combinatorial Optimization, a Cambridge University Press book that presents an iterative method for proving a variety of results in combinatorial optimization.
