UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Variations on sparsifier constructions Xiao, Ke Han


We studied Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava's Twice-Ramanujan Sparsifiers. On this basis, we try to generalize their potential function. Inspired by the idea of non-backtracking matrices, we designed the new potential formula that puts all eigenvalues on the complex plane. Following the construction of the twice Ramanujan sparsifier, we conclude some obstacles must be encountered to improve their bound.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International