Pedro Paredes

On the Expansion of Graphs Degree Type: Ph.D. in Computer Science
Advisor(s): Ryan O'Donnell
Graduated: August 2022

Abstract:

A popular way of analyzing a graph is through spectral properties of its associated matrices, such as the adjacency matrix or the Laplacian matrix. This type of analysis has produced several insights with practical applications in diverse areas, including internet search, clustering and segmentation of data and many more. From a theoretical perspective, spectral graph theory is such a fundamental tool that its applications span virtually the whole field of theoretical computer science. One of the many successes of this area is the notion of graph expansion. A graph is expanding if it is simultaneously sparse and highly connected (meaning that we need to remove a lot of edges to disconnect a large part of the graph.) Since being defined in the '70s, expander graphs have spawned a lot of research with many applications in mathematics, computer science and even physics. This thesis attempts to further the study of these objects by focusing on three fundamental questions:

• How can we construct explicit (i.e. deterministically and efficiently) expanding graphs? We devised an explicit construction of nearly optimal expanding regular graphs of all degrees. We also showed how to use this result to obtain nearly optimal expanding graphs with high girth (i.e. that do not contain small cycles).

• What is the expansion of random graphs drawn from different distributions? We analyzed the expansion of several types of different random graph distributions based on graphs products, like random additive lifts and random abelian lifts.

• How can we leverage expansion in other domains? We showed how to analyze the SDP value of a family of random constraint satisfaction problems (CSPs) and also how to construct explicit nearly linear distance quantum low density parity check (LDPC) and quasi-cyclic LDPC error correcting codes in polynomial time.

Thesis Committee:
Ryan O’Donnell, (Chair, CMU)
Anupam Gupta
Pravesh Kothari
Luca Trevisan (Bocconi University)
Nikhil Srivastava (University of California, Berkeley)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science