Natural Sciences and Engineering Research Council of Canada
Symbol of the Government of Canada

Common menu bar links

Past Winner
2008 NSERC Doctoral Prize

Lap Chi Lau

Computer Science

University of Toronto

The ever-expanding world of communications networks may run more efficiently thanks to doctoral research done by computer scientist Lap Chi Lau at the University of Toronto. Dr. Lau has made outstanding contributions to several challenging theoretical aspects of computer science, which also have important implications for electrical engineering and combinatorial mathematics. His work has earned him an NSERC Doctoral Prize.

Large networks require complex arrays of connections between the various points. Optimizing the total length and number of those connections can make a big difference in how efficiently information gets transmitted. Efficiency is also affected by controlling how information flows through network intersections, similar to the way traffic flow must be managed for road networks. Bottlenecks can develop, just as they do with roads.

The nature and complexity of these problems makes it impossible to apply a simple mathematical formula that can calculate exactly the best way to link networks. Instead, researchers like Dr. Lau specialize in developing algorithms that can offer close approximations of the solution. Working in a challenging area known as combinatorial optimization, he has succeeded in developing a sophisticated new approach to designing these algorithms.

A major focus of his doctoral work involved studying network multicasting, which includes applications such as video conferencing where certain information is expected to reach all users simultaneously.

The recent development of network coding (a process of attaching codes to individual packets of data that allows them to be merged with other data in transit, then identified and reassembled when they reach their destination) has dramatically sped up traffic and improved the performance of multicasting on so-called "directed" networks such as the Internet. (In directed networks, incoming and outgoing data follow separate pathways, regardless of how much data is traveling in either direction. "Undirected" networks allow data to flow in both directions on the same pathway, which offers greater flexibility.)

Attempts to apply network coding to undirected networks, such as wireless networks, proved much less effective, although the reasons were not understood. Dr. Lau's work provided the theoretical explanation and mathematical proof for this phenomenon, thereby preventing designers from going down a blind alley and instead directing their efforts towards other ways of using network coding.

Dr. Lau's research is highly interdisciplinary, as reflected by the fact that he was awarded the Canadian Mathematical Society's Doctoral Prize, the only time a computer science student has won the award. The same research was voted the best student paper at the Symposium on Foundations of Computer Science, a top international computer science conference.