CAREER: Sublinear-Time Graph Algorithms: Foundations, Limitations, and Connections

Graphs are mathematical structures used to model pairwise relationships among objects of various forms. They consist of a collection of "vertices" (the objects) and "edges" (the connections) which connect pairs of vertices. Graphs can model a wide range of applications such as connections in social networks, hyperlinks in the web, and the wiring of the brain.

Many of these graphs are massive. The availability of such large-scale graphs has posed significant challenges in terms of storage, processing, and analysis. At their heart, these tasks require efficient algorithms for various problems defined over graphs.

While designing such graph algorithms has been a cornerstone of computer science research for decades, traditional algorithms often fall short when scaling to massive data. For instance, algorithms designed for massive graphs cannot even afford to read the entire input -- an assumption that is crucial for most traditional algorithms. This project focuses instead on advancing "sublinear-time" graph algorithms, which are specifically designed to process massive inputs.

These are algorithms that uncover meaningful information about their entire input by examining only a small portion of it. The research objectives of this project will be complemented by a comprehensive approach to broadening the outreach of sublinear time algorithms through exploring practical applications, educational initiatives, dissemination efforts, and expanding participation in algorithmic research.

More concretely, this project focuses on three aspects of sublinear time graph algorithms: their foundations, their limitations, and the connections they have to other models of computation. Specifically, this project aims to develop more efficient and ideally optimal sublinear time algorithms for a variety of foundational graph problems such as maximum matching or various graph connectivity problems (such as minimum spanning trees).

The investigator also aims to develop a better understanding of the limitations of sublinear-time graph algorithms by designing systematic approaches to prove (unconditional) query lower bounds for these problems. Finally, many of the recent developments in other models of computation such as dynamic, parallel, or streaming algorithms rely heavily on better sublinear time graph algorithms.

This project aims to take concrete steps towards better understanding these connections and further developing them.

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.