Javascript must be enabled

# Lenka Zdeborova : The spectral redemption comes from no backtracking

A number of computational problems on graphs can be solved using algorithms based on the spectrum of a matrix associated with the graph. On very sparse graphs the traditionally-considered matrices develop spurious large eigenvalues associated with localized eigenvectors that harm the algorithmic performance. Inspired by the theory of spin glasses, we introduce the non-backtracking operator that is able to mitigate this problem. We discuss properties of this operator, as well as its applications to several algorithmic problems such as clustering of networks, percolation, matrix completion or inference from pairwise comparisons.

**Category**: Number Theory**Duration**: 01:34:47**Date**: October 25, 2016 at 4:25 PM**Views**: 109-
**Tags:**seminar, CTMS Adventures In Theory Lectures Seminar

## 0 Comments