CS/ECE Lecture Series

Towards Scalable Spectral Sparsification of Large Graphs, Integrated Circuits and Data Networks

Speaker:Dr. Zhuo Feng
Date: Friday, October 13, 2017
Time: 12:00pm - 1:00pm
Location: 125 Hudson Hall, Duke
Lunch served at 11:45

Abstract

Spectral graph sparsification aims to find ultra-sparse graph sparsifiers (subgraphs) that can well preserve the key eigenvalues and eigenvectors of the original graph Laplacians. Recent theoretic computer science research results show that spectral graph sparsification can lead to the development of a series of ``theoretically nearly-linear-time" numerical and graph algorithms for solving sparse matrices, graph-based semi-supervised learning (SSL), spectral graph partitioning (data clustering), and max-flow problems. For example, spectrally sparsified transportation networks will lead to the development of more scalable navigation or routing algorithms for large transportation systems; spectrally sparsified social networks will enable more effective understanding and prediction of information propagation in large social networks; spectrally sparsified data networks will allow more efficiently storing, partitioning, and analyzing big data networks; spectrally sparsified matrices can be leveraged to more efficiently compute the solution of large linear system of equations; spectrally sparsified circuit networks can lead to more scalable design automation of large integrated circuit systems, etc. However, the long-standing question of whether there exists a practically-efficient spectral graph sparsification algorithm for tackling general large-scale, real-world graphs still remains.

Biography

Dr. Zhuo Feng received the Ph.D. degree in Computer Engineering from Texas A&M University, College Station, TX in 2009. He is currently an associate professor in the Department of Electrical and Computer Engineering of Michigan Technological University. His current research interests include spectral methods for big data and graph problems, heterogeneous parallel computing as well as VLSI design and computer-aided design (CAD). He received a Faculty Early Career Development (CAREER) Award from the National Science Foundation (NSF) in 2014, a Best Paper Award from ACM/IEEE Design Automation Conference (DAC) in 2013, and two Best Paper Award Nominations from IEEE/ACM International Conference on Computer-Aided Design (ICCAD) in 2006 and 2008. He is the principle investigator of the CUDA Research Center at Michigan Technological University named by Nvidia Corporation. He has served on the technical program committees of major international conferences in the areas of electronic design automation (EDA) and VLSI design, including DAC, ICCAD, ASP-DAC, ISQED, etc. In 2016, he co-founded a startup, LeapLinear Solutions, to provide highly scalable solutions for big data and graphs problems based on the latest breakthroughs in spectral graph theory.

Hosted by:
Dr. Hai (Helen) Liu