Graph approximation and local clustering

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=299kgffszEM


Duration: 1:06:19
993 views
15

We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms. The need to quickly partition a graph leads us to the local clustering problem: given a vertex in a massive graph, output a small cluster near that vertex in time proportional to the size of the cluster. We use all these tools to design nearly-linear time algorithms for solving diagonally-dominant systems of linear equations, and give some applications. This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Gremban, Miller, Koutis, Emek, Elkin, Andersen, Chung, Lang, Daitch, Srivastava and Batson.



Other Videos By Microsoft Research


2016-09-06iBrain: Surviving the Technological Alteration of the Modern Mind
2016-09-06Child Sexual Abuse: Facts & Myths - What You Need To Know To Keep All Children Safe
2016-09-06Conversational Turn-Taking as a Dynamic Decision Process [1/15]
2016-09-06Directing the Datacenter with Machine Learning
2016-09-06The Unfinished Game: Pascal, Fermat & the 17th Century Letter that Made the World Modern
2016-09-06Cryptography: From Theory to Practice
2016-09-06A Cryptographic Compiler for Information-Flow Security
2016-09-06STAIR: The STanford Artificial Intelligence Robot project
2016-09-06Deniable Authentication on the Internet
2016-09-06Scalable Virtual Machine Multiplexing
2016-09-06Graph approximation and local clustering
2016-09-06The Subprime Solution: How Today's Global Financial Crisis Happened, and What to do about It
2016-09-06Real-Time Visual Localisation and Mapping with a Single Camera
2016-09-06Keeping Fit with the Jetsons
2016-09-06Linguistic Visualization for Fun and Profit
2016-09-06Rapid Language Portability for Speech Processing Systems
2016-09-06Context-Aware Scheduler: Avoiding Unfavorable Scheduling to Improve Virtual Machine Performance
2016-09-06The Bulk Multicore Architecture for Programmability
2016-09-06Part I: Improved mixing time bounds for the Thorp shuffle and L-reversal chain
2016-09-06The Lightness of Being: Mass, Ether and the Unification of Forces
2016-09-06Bilinear Complexity of the Multiplication in a Finite Extention of a Finite Field


Tags:
microsoft research