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 heatkernels are  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.

　　Bio:　　

　　He Sun is a tenured lecturer in the Department of Computer Science, University of Bristol. Prior to that, he was a Simons-Berkeley Research Fellow at UC Berkeley, and a senior researcher at Max Planck Institute for Informatics, where he led the research group on Combinatorics, Randomness, and Computing. He obtained his PhD in 2010 from Fudan University.　　

　　His main research interest is the design and analysis of algorithms. Topics he has worked on include computational geometry, streaming algorithms, distributed computing, spectral graph theory, and machine learning.