Abstract

Heat kernels are one of the most fundamental concepts in physics and mathematics. In physics, the heat kernel is a fundamental solution of the heat equation and connects the Laplacian operator to the rate of heat dissipation. In spectral geometry, many fundamental techniques are based on heat kernels. In finite Markov chain theory, heat kernels correspond to continuous-time random walks and constitute one of the most powerful techniques in estimating the mixing time.

In this talk, we will briefly discuss this line of research and its relation to heat kernels in graphs. In particular, we will see how heat kernels can be used to design the first nearly-linear time algorithm for finding clusters in real-world graphs. Some interesting open questions will be addressed as well.

This is based on the joint work with Richard Peng (MIT), and Luca Zanetti (University of Bristol). Parts of the results of this talk are to appear in COLT 2015 .