University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Heat kernels in graphs: A journey from random walks to geometry, and back

Heat kernels in graphs: A journey from random walks to geometry, and back

Add to your list(s) Download to your calendar using vCal

  • UserHe Sun, University of Bristol
  • ClockFriday 12 June 2015, 14:00-15:00
  • HouseFW26.

If you have a question about this talk, please contact Jonathan Hayman.

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 .

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity