The bit-operation complexity of matrix multiplication and of all pair shortest path problem

AbstractAn N × N matrix product can be evaluated with precision E > 0 in O(Ns+ϵ log (M/E) log log (M/E) log log log (M/E)) bit-operations, ϵ > 0 arbitrary, M the maximum absolute value of the entries of given matrices, O(ns) the arithmetic complexity of n × n matrix multiplication, s < 2.496. The shortest path problem for a graph with N vertices whose edges have non-negative integer costs and all shortest distances are bounded by H can be solved in O(Nsϵ+H) bit-operations