AF: Small: Collaborative Research: New Challenges in Graph Stream Algorithms and Related Communication Games

Dartmouth College, Hanover NH

Investigators

Abstract

Computational problems in many domains call for analyzing interactions among a very large number of entities. For instance, the friendship links in a globe-spanning social network contain a vast amount of knowledge. Detailed analyses of these links can drive research in the social sciences, aid security analysis and intelligence gathering, and guide infrastructure planning. Some other important examples of large networks (graphs, in mathematical parlance) that hide a wealth of information are the networks of genes and neurons in biology, the network of web pages, and the network of geometric and physical relationships between stars and galaxies. Further, many such graphs are continually evolving as links appear and disappear, potentially necessitating repeated costly computation. It is usually infeasible or inefficient to perform computations on graphs this large while holding them entirely in memory. To address this broad challenge, over the last decade or so, researchers including this project's investigators have developed algorithmic techniques known as streaming and sketching to compute more efficiently on large data sets, including large graphs. A streaming algorithm treats its input as an ordered sequence of values, each of which can be read only once. Sketching refers to techniques for summarizing a stream of data using memory much smaller than the data stream. This project will (1) develop novel streaming and sketching algorithms for graph problems that are fundamental enough to have broad applicability and (2) develop the underlying mathematical theory of such algorithms to better understand their possibilities and limitations. At a technical level, one major goal of this project is to attack basic directed graph problems in the streaming model, from both upper and lower bounds perspectives: the existing theory is mostly focused on undirected graphs. Another goal is to deeply understand the role of randomness in solving graph problems that admit efficient linear sketches: such understanding is currently limited to problems from basic statistics. The theory of streaming and sketching algorithms is closely tied to communication complexity, which studies protocols for solving problems (sometimes called games) where the input is distributed across two or more sites. Accordingly, this project will seek new protocols or lower bounds for some such communication games and design novel communication games that address aspects of streaming algorithms specific to graph problems. The investigators will leverage the geographical proximity of their respective universities to build more formal ties between their respective theoretical computer science research groups, including an annual day-long workshop. They will continue their established history of developing pedagogical materials on the research topics included in or closely related to this project. 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.