Invited ICDT Lecture

We are very pleased to announce the invited ICDT2023 tutorial speaker.

Subgraph counting and graph orientations: the gift that keeps on giving
by Seshadhri Comandur

Abstract: Subgraph counting is a fundamental problem that spans many areas in computer science: database theory, logic, network science, data mining, and complexity theory. Given a large input graph G and a small pattern graph H, we wish to count the number of occurrences of H in G. In recent times, there has been a resurgence on using an old (maybe overlooked?) technique of orienting the edges of G and H, and then using a combination of brute-force enumeration and dynamic programming. The practical performance of these algorithms is surprisingly good, and the algorithms actually have provable running time bounds. These orientation techniques appear to give the best of both worlds. There is a rigorous theoretical explanation behind these techniques, and they also have excellent empirical behavior (on large real-world graphs). Time and again, graph orientations help solve subgraph counting problems in various computational models, be it sampling, streaming, distributed, etc. My talk will be about the graph orientation technique and how it seems to keep on giving.

C. Seshadhri (Sesh) is a professor of Computer Science at the University of California, Santa Cruz. Prior to joining UCSC, he was a researcher at Sandia National Labs, Livermore in the Information Security Sciences department, during 2010-2014. His primary interest is in mathematical foundations of big data, especially modeling and algorithms. By and large, Sesh works at the boundary of theoretical computer science (TCS) and data mining. His work spans many areas: sublinear algorithms, graph algorithms, graph modeling, scalable computation, and data mining. In the theory world, his work has resolved numerous open problems in monotonicity testing and graph property testing. A number of his papers in the interface of TCS and applied algorithms have received paper awards at KDD, WWW, ICDM, SDM, and WSDM. He received the 2019 SDM/IBM Early Career Award for Excellence in Data Analytics. Sesh got his Ph.D from Princeton University and spent two years as a postdoc in IBM Almaden Labs.