Triangle Detection in Worst-Case Sparse Graphs via Local Sketching

Hongyi Duan, Jian'an Zhang

We present a non-algebraic, locality-preserving framework for triangle detection in worst-case sparse graphs. Our algorithm processes the graph in $O(\log n)$ independent layers an…