A Spectral Bound on Small-set Expansion for a Directed Graph

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Presentation

Title: "A Spectral Bound on Small-set Expansion for a Directed Graph"

by

Mr. TAN, Shuhao 


Abstract:

Small-set Expansion is a powerful tool for reduction in complexity theory. 
Through Spectral Graph Theory, researchers have found good ways to attack 
it on a regular undirected graph. This thesis lessens restrictions on the 
target graph and presents a more general result. We employ techniques in 
Linear Algebra and Analysis and acquire a spectral bound on a nonregular 
directed graph with additional parameterized conditions. This allows easier 
reduction to Small-set Expansion.

Keywords: Spectral Graph Theory, Small-set Expansion, Directed Graph


Date                 : 30 April 2016 (Saturday)

Time                 : 9:30am to 10:15am

Venue                : Room 5510 (lift 25/26)

Advisor              : Dr. Ke YI
                              
2nd Reader           : Prof. Cunsheng DING