Theoretical and Applied Data Science Seminar - Andrew McGregor

Thursday, December 17, 2020 - 12:00pm to 1:00pm

Presenter: Andrew McGregor

Andrew McGregor

Title: Recent Results on Cycle Counting in the Data Stream Model

Abstract: Estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. From the theoretical perspective, it is a convenient problem to explore the efficacy of various sampling techniques and to understand the limits of stream computation. From an applied perspective, the frequency of cycles and other subgraphs captures interesting structural properties of massive real-world graphs. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this talk, we survey recent work in all these models.

Bio: Andrew McGregor is an Associate Professor at the University of Massachusetts, Amherst. He received a B.A. degree and the Certificate of Advance Study in Mathematics from the University of Cambridge and a Ph.D. from the University of Pennsylvania. He also spent a couple of years as a post-doc at UC San Diego and Microsoft Research SVC. He is interested in many areas of theoretical computer science and specializes in data stream algorithms, linear sketching, and communication complexity. He received the NSF Career Award in 2010, the College Outstanding Teacher Award in 2016, and the ACM PODS Alberto O. Mendelzon Test-of-Time Award in 2020. He currently directs the UMass TRIPODS Institute on the Theoretical Foundations of Data Science.

After the presentation, there will be a short time for discussion and questions afterwards.