[Colloq] Hiring Talk - Lap Chi Lau - Algebraic techniques in fundamental graph problems - March 24, 10:30am, 366 WVH

[Jessica Biron]

Speaker: Lap Chi Lau 



Title: Algebraic techniques in fundamental graph problems 



Time/Location: Monday, March 24, 10:30 AM in 366 WVH 



Abstract: 



Graph partitioning, graph connectivity, and network design are fundamental graph problems with applications in various areas of computer science and engineering. Designing good algorithms for these problems has received considerable attention in theoretical computer science in the past decades. In this talk, I will show that some simple algebraic ideas are surprisingly powerful in studying these combinatorial problems, from new analyses of existing algorithms to the design of faster algorithms and better approximation algorithms. 



- In practice, the spectral method is one of the most popular heuristics for graph partitioning with good empirical performance in applications. In theory, however, its worst case performance is poor, and it has been an open question to explain this discrepancy. We answer this question by giving a new analysis of the spectral method using higher eigenvalues of graphs. 



- Network coding is a novel method for information transmission in computer networks. We show that this method can be used to design faster algorithms for computing graph connectivity. Interestingly, the ideas can also be used to design faster algorithms for computing matrix rank, showing some interactions between ideas in graph theory and linear algebra. 



- We present a general iterative method to design near-optimal approximation algorithms for many network design problems and beyond. 

The key idea is to use linear independence to analyze the extreme point solutions of the linear programming relaxations. 





Biography 



Lap Chi Lau is an associate professor in the Department of Computer Science and Engineering at The Chinese University of Hong Kong. He was a visiting researcher in Microsoft Research New England during January-June 2009. 



His research interests are in algorithm design and theoretical computer science. He has worked primarily in designing algorithms for graph problems, using techniques from algebraic, probabilistic and combinatorial methods. He is also interested in theoretical problems from other areas. 



Lap Chi obtained his PhD from the University of Toronto. During his PhD study, he received the best student paper award in FOCS 2004 and the Microsoft Research Fellowship. For his thesis work, he received the Doctoral Prize 2007 from the Canadian Mathematical Society, and the Doctoral Prize 2008 from the Natural Sciences and Engineering Research Council of Canada. 



Host: Rajmohan Rajaraman 







Jessica Biron 
Administrative Assistant – Co-op and Advising 
College of Computer and Information Science 
Northeastern University 
202 West Village H 
617-373-5204 
bironje at ccs.neu.edu 
http://www.ccs.neu.edu/