Algorithms for Massive and Stochastic Graphs

With the rapid advances in technology, real-world data sets have embraced an ever-expanding complexity that the traditional algorithms cannot address. One challenge is the massive size of these data sets which demands highly resource efficient algorithms. This has resulted in a growing interest in designing streaming and massively parallel (e.g., MapReduce) algorithms that take very few rounds of computation/communication and a substantially smaller central space than the input size. Another (relevant) challenge is the inherent uncertainty in the data sets for which the algorithm has to conduct — often expensive — queries without being completely aware of the actual input. This has led to a long line of research in designing stochastic optimization algorithms.In this thesis, we propose and analyze algorithms for fundamental graph problems such as maximum matching, minimum spanning tree, minimum bisection, and graph clustering methods (such as single-linkage and its variants) in the aforementioned models. These algorithms improve over the state-of-the-art via the tools, techniques, and most importantly, combinatorial observations that we demonstrate throughout this thesis. Although our main focus is on the theoretical guarantees of the proposed algorithms, they are also arguably simple and practical. We exhibit this via experiments on real-world graphs and internal data sets of giant tech companies such as Google.

Examining Committee:

Chair: Dr. MohammadTaghi Hajiaghayi Dept. rep: Dr. John Dickerson Members: Dr. Aravind Srinivasan Dr. Vahab Mirrokni