On Graph Sparsifiers, Graph Sketches and Fast Linear Solvers

PhD Thesis Proposal Defence


Title: "On Graph Sparsifiers, Graph Sketches and Fast Linear Solvers"

by

Mr. Bo QIN


Abstract:

Most graph algorithms run faster, sometimes by orders of magnitude, on 
sparse graphs (that contain fewer edges).  By approximating a dense input 
graph by a suitable sparse graph or other data structure, one can improve 
the algorithm's computation and storage efficiency. With this motivation, 
this thesis concentrates on the problem of how to construct a compact data 
structure that closely represents a given graph, as well as its related 
applications.

Our first focus is graph sparsification. The generic graph sparsification 
problem is to approximate a given graph by a sparse graph (i.e., a graph 
sparsifier) on the same vertex set but retaining only a smaller subset of 
edges.  Such a sparsifier usually preserves, with bounded error, some 
quantitative properties of the original graph, making it an appropriate 
candidate to replace the old graph in some computations. We present faster 
randomized and deterministic algorithms for constructing graph sparsifiers 
that preserve (up to small error) the value of every Laplacian quadratic 
form.

We then extend the idea of graph sparsification to creating a novel data 
structure—graph sketches.  Graph sketches differ from graph sparsifiers in 
two aspects: (i) Sketches can be any data structure, not limited to 
graphs, and (ii) Sketches only preserve the value of every fixed Laplacian 
quadratic form, with high probability. We demonstrate lower bounds on the 
space size of sketches for storing graphs, positive semi-definitive (PSD) 
matrices, and general real matrices. Furthermore, we present an algorithm 
for constructing nearly optimal graph sketches, which uses much less 
storage than even the graph sparsifier.

Finally, we investigate the problem of designing solvers for linear 
systems of equations, an important application related to graph 
sparsification. We develop a new algorithm for solving a linear system for 
a special class of PSD matrices, those which can be decomposed into the 
sum of two almost commuting matrices. Our solver runs in time nearly 
linearly depending on the input size, beating previous best solvers.


Date:			Wednesday, 28 September 2016

Time:                  	10:00am - 12:00noon

Venue:                  Room 1504
                         (lifts 25/26)

Committee Members:	Prof. Mordecai Golin (Supervisor)
  			Prof. Siu-Wing Cheng (Chairperson)
 			Dr. Sunil Arya
  			Dr. Ke Yi


**** ALL are Welcome ****