Close

Presentation

On the Accuracy and Efficiency of Approximate Triangle Counting via Randomized Numerical Linear Algebra
DescriptionWe study two algorithmic approaches to approximate triangle counting and compare their accuracy and efficiency. The first one is based on randomized matrix-matrix multiplication, which can be faster, simpler, and more parallelizable on modern processors. The second is based on trace estimation, which produces estimates with lower variance and greater accuracy.