Theory Lunch Seminar

Wednesday, November 25, 2015 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates & Hillman Centers

Speaker:

SHEN CHEN XU, Ph.D. Student http://www.cs.cmu.edu/~shenchex/

Event Website:

http://www.cs.cmu.edu/~theorylunch/20151125.html

For More Information, Contact:

dwajc@cs.cmu.edu

Problems about distances in graphs have proved to be difficult to parallelize. Compared to the sequential results, we often lose out in at least one aspect of solution quality, work, or depth. In this talk we give an approach that is centered around a graph decompositions scheme. We will describe a parallel graph clustering algorithm using exponential start time, and apply it to obtain work efficient spanner construction and the shortest path distance approximation. About the Speaker Sponsored in part by Yahoo! Labs

Keywords:

Seminar Series