You are here
Theoretical and Applied Data Science Seminar - Andrew McGregor
Presenter: 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.