Grant: Discovery Grants Program - Individual

Massive graphs abound: web pages and hyperlinks, neurons and synapses, papers and citations, or social networks and friendship links, to name a few. Yet, traditional algorithmic approaches are inadequate for effectively processing such massive graphs due to their sheer size and evolving nature. Consequently, there is a rapidly growing interest in developing algorithms that explicitly account for the challenges of processing massive graphs. Graph streaming algorithms have emerged as a remarkably successful theoretical model for addressing these challenges. These algorithms process input graphs by making one or a few passes over their edges while using a limited memory. The advantages of streaming algorithms are threefold. Firstly, due to their inherent I/O-efficiency, graph streaming algorithms can be directly translated into practical algorithms on many existing processing platforms. Secondly, they share close ties with several other theoretical models of computation on massive graphs, often leading to the development of efficient algorithms in those models as well. Finally, a unique advantage of graph streaming algorithms is that we also have a powerful tool for proving impossibility results for them: communication games. These impossibility results can provide invaluable insights and guide us in designing better algorithms or incorporating more realistic assumptions. This proposal focuses on understanding the powers and limitations of graph streaming algorithms for several foundational problems such as coloring, matching, reachability, and shortest path. These are among the most studied problems in theoretical computer science with a broad range of applications in computer science, combinatorics, optimization, and operation research. Despite the significant attention, many fundamental questions regarding these problems have remained unanswered in the streaming model. We will investigate several of these questions in this proposal. These questions, beyond their own intrinsic value, are also chosen as a representative of the current limits on our knowledge - progress on any of these questions will likely lead to an avalanche of progress in the entire area. The key to these investigations will be development of novel algorithmic and analytical techniques in the study of graph streaming algorithms and building connections to various other areas of theoretical computer science. We also plan to bring these new insights into practice. The problems in the proposal are of both theoretical and practical significance. This proposal will bridge the existing gaps in our knowledge of these foundational problems and lead us to a deeper understanding of graph streaming algorithms. HQP trained in this project will also gain valuable and sought-after skills in the design and analysis of scalable algorithms in particular, and theoretical computer science in general, and will be well positioned for future jobs in either academia or industry.