Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Tayla Eden, Massachusetts Institute of Technology

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.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home