Seminar Details
Faster K-clique Counting in Bounded Arboricity Graphs
- Start Date: November 4, 2020
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Organizers: Sepehr Assadi || Swastik Kopparty
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Tayla Eden - Massachusetts Institute of Technology
- Event Location: Online Event
- Event Additional Info: <p>The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p> </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home" target="_blank">https://sites.google.com/view/dimacs-theory-seminar/home</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Abstract:
I will discuss a sublinear-time algorithm for approximately counting the number of k-cliques in bounded arboricity graphs. Counting cliques (and triangles in particular) is a fundamental task in graph algorithms with a long line of theoretical results as well as numerous applications. The arboricity of a graph is a measure to its \`\`everywhere sparseness'' and the family of bounded arboricity graphs plays an important role both in theory and in practice. Therefore parameterizing the complexity of the algorithm is of great interest.