Towards a spectral algorithm for Small-set expansion and Graph multi-partitioning

Anand Louis (Mentors: Santosh Vempala, Prasad Raghavendra, CS and Prasad Tetali, Math+CS) - The problem of finding the sparsest cut in graphs is a well known and intensively studied problem.  We are interested in applying spectral and semi-definite programming based techniques to some generalizations of the sparsest cut problem. In particular we hope to relate the small set expansion and other multipartitioning coefficients to higher eigenvalues of graphs. Computation of these parameters is also interesting because of their close connection to Unique Games (Raghavendra, Steurer 2010). Computation of these parameters is known to be NP-hard.