Institute of Information Science, Academia Sinica

A main challenge to compute over a large data set is to organize data. For many problems, extracting a sketch of the large data set is sufficient to perform the computation, so there is no need to memoize the entire input. For problems that are impossible to compute without memoizing the entire input, one may appeal to modern databases, which are provable much better than classical ones by taking advantage of asymmetric read-write costs of secondary storage.

In this talk, I will present how sketches work for some fundamental graph and ge-ometry problems, such as k-connectivity, spanning trees (MaxLeaf, BFS, and DFS), degeneracy, and convex hull. I will also show how communication complexity can be used to prove when sketches cannot work. If sketches cannot work, one can still gain a significant speedup by organizing data using Bε-trees. Finally, derandomizing a framework of algorithms to fetch sketches by majority-free sets will be presented.

Meng-Tsung Tsai received his BS and MS degrees in Computer Science from National Taiwan University in 2006 and 2008, and PhD degree in Computer Science from Rutgers University in 2017. Since August 2017, he is an assistant professor in Department of Computer Science at National Chiao-Tung University. His research interests include data-intensive algorithms, lower bound techniques, graph theory and database theory.