Spectral algorithms for large graphs: where theory and practice meet

Dr Ioannis Kuotis
University of Puerto Rico, Rio Piedras


Abstract

We will discuss recent progress in the theory and algorithms for three related problems: graph sparsification, graph partitioning and linear system solving. The combined effect of these advances has led to very fast 'spectral' algorithms that are provably near-optimal and have been successfully applied to problems on graphs with millions of nodes. These recently discovered algorithms constitute an evolution of heuristics that were previously introduced and pursued in various applied contexts. In turn, their enhanced effectiveness enables further experimentation that potentially opens the way to new applications in data science, as well to new theoretical discoveries. We will thus argue that spectral algorithms are an exemplary case of a successful synergy between theory and practice.