Abstracct

In the era of big data, massive datasets emerge in almost every application domain. Processing data in a traditional way, which takes at least time and space linear in the input size, becomes more-and-more commercially unaffordable. Important topics within sublinear algorithms include parallel computation (sublinear time), streaming algorithms (sublinear space), and communication complexity (sublinear communication), to name a few. In this talk, I will investigate the above topics through the lens of two fundamental problems: graph connectivity and bipartite matching. For graph connectivity, I will start with the simplest possible parallel algorithm with running time O(log n), then introduce the recent breakthroughs of how to break the O(log n) barrier. I will also show how to achieve o(log n) time and linear work, which is optimal. For bipartite matching, I will start with a simple approximate streaming algorithm whose correctness proof is based on combinatorial auctions, then I will introduce our recent work that finds the exact bipartite matching in the semi-streaming model that takes sublinear passes unless the graph is extremely dense.

About the speaker

Cliff Liu is an associate professor at Shanghai Jiaotong University. He was a postdoc in CMU theory group and obtained his PhD from Princeton. His research is around sublinear algorithms, graph algorithms, and data structures. Cliff was a recipient of the Gordon Y.S. Wu Fellowship and NSFC Science Fund Program for Distinguished Young Scholars.