CAREER: Fast Scalable Graph Algorithms

Graphs, representing one of the most intuitive and natural methods for depicting data relationships, are integral to numerous applications. They are particularly crucial in domains like Web search, neural and social network analysis, and in representing complex knowledge. The scale of modern graphs, coupled with new cloud-based processing infrastructure, has exposed a need to develop more efficient methods to process large graphs. This project is driven by a crucial question: "What techniques lead to extremely efficient, scalable algorithms?" The research objective is to advance the design of efficient, large-scale graph algorithms for the massively parallel and distributed computational frameworks that comprise modern data centers. The project includes an educational plan that includes an annual programming competition open to high school students, as well as undergraduates aimed at fostering an algorithm-design mindset and at attracting diverse students into computer science. Elements of the contest will also inform the principle investigator's courses. The project targets fundamental questions by studying core graph theory problems -- such as matchings, vertex covers, and densest subgraphs -- in the context of large-scale modern frameworks for parallel and distributed computation. This project aims to produce innovative methods and more efficient algorithms for processing massive graphs by developing new "sparsification in computation" techniques whose main aim is to perform a computational task by considering carefully crafted subsets of the input graph. The project outlines two main thrusts, namely (1) sparsification in computation for the sublinear regime, and (2) sparsification in computation for the linear regime. The algorithmic challenges tackled in this project will focus on various large-scale regimes, particularly concerning the relationship between the sizes of input graphs and the capacities of the available computing units. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.