Explore parallel approximate undirected shortest paths algorithms in this theory seminar presented by Peilin Zhong from Columbia University. Delve into the concept of low hop emulators and their application in solving graph problems efficiently. Learn about the Bellman-Ford algorithm, hopset construction, and the "Law of Amateur" in graph theory. Discover applications in submillimetre and strong submillimetre problems, and understand the highway example used to illustrate key concepts. Analyze the construction and performance of these algorithms, and consider open problems in the field. This comprehensive lecture, recorded on February 25, 2020, includes closed captions and is part of the Paul G. Allen School's theory seminar series.
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Paul G. Allen School via YouTube
Overview
Syllabus
Introduction
Problem Statement
Bellman for Organ
Hopset
Original Construction
Main Question
Results
Law of Amateur
Local Amateur
Applications
Submillimetre
Strong Submillimetre
Highway Example
Construction
Analysis
Open Problems
Taught by
Paul G. Allen School
