The Sketching Complexity of Graph and Hypergraph Counting

10 Dec
Theory of Computation Seminar
Eric Price, University of Texas at Austin
Monday, December 10, 2018 - 1:30pm to 2:30pm
Pierce Hall 213 (Brooks Room)

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings have not been well understood. This talk will revisit the subgraph counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. 

I will describe a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph H in a bounded degree graph G presented as a stream of edge updates, showing that the space complexity of the problem is governed by the fractional vertex cover number of the graph H.  The main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound.

Joint work with John Kallaugher and Michael Kapralov.

Speaker Bio: 

Eric Price is an assistant professor in the Department of Computer Science at UT Austin, where he studies how algorithms can produce more accurate results with less data.  He received a Ph.D. in computer science from MIT in 2013. Eric's research was featured in Technology Review's TR10 list of 10 breakthrough technologies of 2012, his thesis received a George M. Sprowls award for best doctoral thesis in computer science at MIT, and he has received an NSF CAREER award. Two themes of his research are adaptivity, where initial data can guide future data collection, and signal structure, where a structural assumption can yield provable improvements in space or sample complexity.

Carol Harlow