``Fast Estimation of Diameter and Shortest Paths
 		       (without Matrix Multiplication)''

Consider the problem of computing all-pairs shortest paths in an
undirected, unweighted graph with $n$ vertices and $m$ edges.  Using
fast matrix multiplication, this problem can be solved in time
$\~O(n^\omega)$, where $\omega$ is the exponent in the running time of the
fast matrix multiplication algorithm.  Not only are these algorithms
infeasible in practice, they are unsatisfying in that by ignoring the
combinatorial structure of these problems they hide the nature of the
solution.  We present a purely combinatorial algorithm for approximating
all-pairs shortest paths (and thus diameter) -- to within a additive
constant error -- in $\~O(n^2.5)$ time. Implementation results show that
this algorithm is significantly faster than prior approaches, with only
a small loss in accuracy.  Open questions are whether the error can be
eliminated, and if the running time can be reduced below the current
exponent for fast matrix multiplication (which is currently $2.376$).