PhD Defense: Algorithms for Massive Data: Fundamental Graph Problems Revisited

Although computing power has advanced at an astonishing rate, it has been far outpaced by the growing scale of data. Inherent assumptions of traditional algorithms, such as the possibility of storing the whole input in a single machine, do not hold for large-scale problems where even a linear-time algorithm may be prohibitive. Motivated by this challenge, we revisit a number of fundamental graph problems and devise new algorithms for them whose resources---such as time, space, or communication---are sublinear in the input size.In this thesis, we study (i) massively parallel computation algorithms where the workload is distributed to several machines each with sublinear space/communication, (ii) sublinear-time algorithms that process the input while reading a small fraction of it, (iii) streaming algorithms that take only few passes over the input having access to a sublinear space, and (iv) dynamic algorithms that address changes to the input in sublinear time.We propose new algorithms for central graph problems such as matching, independent set, vertex cover, and connectivity in these models that substantially improve upon the state-of-the-art and are in many cases optimal. Many of our algorithms build on model-independent tools and ideas that lead to improved bounds in more than one of the aforementioned settings.
Examining Committee:

Chair: Dr. MohammadTaghi Hajiaghayi Dean's rep: Dr. Alexander Barg Members: Dr. Avrim Blum
Dr. Sanjeev Khanna Dr. David Mount Dr. Aravind Srinivasan Dr. Madhu Sudan