Computer Science Seminar: Zihan Tan

Description

Zihan Tan, a postdoctoral associate at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University, will give a talk titled "Modern Algorithms for Massive Graphs: Structure and Compression" for the Department of Computer Science.

Abstract:

In the era of big data, the significant growth in graph size renders numerous traditional algorithms, including those with polynomial or even linear time complexity, inefficient. Therefore, we need novel approaches for efficiently processing massive graphs. In this talk, Zihan Tan will discuss two modern approaches towards this goal: structure exploitation and graph compression. He will first show how to utilize graph structure to design better approximation algorithms, showcasing his work on the Graph Crossing Number problem. He will then show how to compress massive graphs into smaller ones while preserving their flow/cut/distance structures, thereby obtaining faster algorithms.