[Colloq] Reminder: Hiring talk Monday morning

[Rajmohan Rajaraman]

----- Forwarded Message -----
From: "Jessica Biron" <bironje at ccs.neu.edu>
To: "colloq" <colloq at lists.ccs.neu.edu>
Sent: Tuesday, March 18, 2014 10:12:33 AM GMT -05:00 US/Canada Eastern
Subject: [professors] [Colloq] Hiring Talk - Lap Chi Lau - Algebraic techniques in	fundamental	graph problems - March 24, 10:30am, 366 WVH

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