Abstract: The vast growth of big graphs such as web graphs, social networks, and biological networks call for data streaming or graph streaming algorithms. These algorithms read an input graph as a sequence of edge insertions and deletions and maintain a summary using memory sublinear in the input size. This summary is used to analyse properties of the graph and to answer queries about it. In the classical streaming model, the entire input stream is assumed to be fixed by an adversary before the algorithm reads it. Many classical streaming algorithms, however, fail if the input stream is continued by an adaptive adversary based on past outputs received. This is the so-called "adversarially robust" streaming model. Now, many problems turn out to be provably impossible to solve in sublinear space in these settings. It is then natural to consider an enhanced streaming setting that models outsourced computation: a space-bounded client delegates the computation to a space-unbounded but untrusted cloud service and just needs to verify the solution that it sends. This is called the "annotated streaming" model.
My research focuses on designing space-efficient algorithms for graph problems in the classical, robust, and annotated streaming settings, as well as proving lower bounds on the space requirements. In this talk, I shall give an overview of my results and provide an essence of the models by focusing on one result from each of them. I shall conclude with some future research directions and open questions.
Bio: Prantar Ghosh is a fifth-year Ph.D. student in the Computer Science department of Dartmouth College. Previously, he completed an M.Sc. in Computer Science (2017) and B.Sc. in Mathematics and Computer Science (2015) at the Chennai Mathematical Institute (CMI) in India. His research interests lie broadly in Theoretical Computer Science, especially in graph algorithms. He is currently working on designing efficient graph algorithms in memory-restricted settings such as data streaming, stream verification, and graph query, as well as in the dynamic graph setting. He is also interested in communication complexity, FPT algorithms, and combinatorial graph theory.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.