All pairs shortest path in quadratic time with high probability

Date

July 30, 2010

Overview

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices with edge weights chosen independently and uniformly at random from [0,1] is O(n2), in expectation and with high probability. This resolves a long standing open problem.

Joint work with Y. Peres, D. Sotnikov and U. Zwick

Speakers

Benny Sudakov

Benny Sudakov received his Ph.D. from Tel Aviv University, had appointments at Princeton University and the Institute for Advanced Studies in Princeton and is currently a Professor of Mathematics in UCLA. His main interests are Combinatorics and its applications in Computer Science.

‚Äč