Data Science Seminar
Putting Parameterization into Practice
Shweta Jain
Putting Parameterization into Practice
| When | Wednesday, January 25, 2023, 10:45 AM – 11:45 AM (MT) |
|---|---|
| Where | MEB 3147 |
Abstract
Graphs are everywhere: social networks, protein interaction networks, citation networks, epidemic spread networks. Applications that use these graphs have progressively become more sophisticated, relying on getting fast and accurate solutions to graph-theoretic problems, many of which are NP-Hard. However, the sizes of today’s graphs easily run into millions of vertices and edges, if not more. As a result, many classic algorithms are infeasible for such graphs.
Fortunately, real-world graphs across different domains show a lot of common characteristics such as an abundance of triangles, low average distance between vertices (small-world property), low degeneracy (a measure of the sparsity of edges) etc. which we can leverage to design algorithms that are provably efficient given those parameters. I will demonstrate this in the context of clique counting and decomposition of graphs, which has applications in community detection, spam detection, fraud detection, gene module detection etc. The new algorithms not only massively improve the performance in practice but also improve our theoretical understanding of real-world graphs and help to bridge the gap between theory and practice.
Speaker
Shweta Jain
Utah SoC
Shweta Jain is a Computing Innovation Fellow (CIFellow) at the University of Utah working with Prof. Blair D. Sullivan. She was previously a postdoc at the University of Illinois, Urbana-Champaign and prior to that she completed her Ph.D. in Computer Science at the University of California, Santa Cruz (UCSC), advised by Prof. Seshadhri Comandur. Her research interests are in graph mining, parameterized algorithms, randomized and approximation algorithms, and algorithms for massive data and the goal of her research is to use these tools to design algorithms that work well in practice and have provable guarantees. Her work has been recognized by two Best Paper Awards, the SIGKDD Best Dissertation Runner-Up Award 2021, and the Best Dissertation Award 2020 of the Computer Science Department at UCSC. She was also chosen as a Rising Star of EECS 2020.
Tags: algorithms & theory biology & genomics networks & graphs
Part of the Data Science Seminar. Something wrong on this page? Edit _data/talks/2023-01-25-shweta-jain.toml.