Refreshments are available starting at 10:30 a.m. The seminar will begin at 10:45 a.m.
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.
Speaker Biography
Zihan Tan is a postdoctoral associate at DIMACS, Rutgers University. Before joining DIMACS, he obtained his PhD from the University of Chicago, where he was advised by Julia Chuzhoy. He is broadly interested in theoretical computer science, with a focus on graph algorithms and graph theory.