Fall 2013

The Trials and Tribulations of Tractably Counting Triangles

Wednesday, November 20th, 2013 3:25 pm3:50 pm

Add to Calendar

The humble triangle is well known to be an important feature in large social networks, and it forms the basis of many data analyses and algorithms. Nonetheless, getting accurate triangle counts in a large, especially streamed, graph is a big challenge. I will give some recent advances in this problem for various settings. This is one of those lucky situations where theory and practice can be unified: interesting theoretical ideas for triangle counting have a practical impact.