Spectral Graph Theory ? Spectral Sparsification in different settings

Graphs constitute the most fundamental objects for storing data in our current days. Spectral graph theory represents the study of algebraic properties of matrices related to graphs. Over the past decade, the techniques developed in spectral graph theory have successfully surpassed crucial barriers encountered by purely combinatorial algorithms and have led to many practical applications.

One of the main focuses in spectral graph theory is spectral sparsification, which is a spectral approximation of an arbitrary undirected graph by a sparse subgraph that can be constructed almost as fast as reading the original graph. Since most algorithms run faster on sparse graphs and it is more space-efficient to store sparse graphs, spectral sparsification has become an extremely powerful tool in designing fast algorithms for machine learning and optimisation problems.

In this project we will improve the current state-of-the-art for spectral sparsification in different settings. This include designing more practical algorithms for constructing spectral sparsifiers and improving the current constructions of subgraph sparsifiers. We will also study the algorithmic Kardison-Singer problem, which can be viewed as a stronger version of spectral sparsification. Finally, the project will study algorithms for constructing spectral sparsifiers in the dynamic and streaming settings, with better update and query time in the worst case.