Conditional lower bounds on the running time of the single source shortest path problem
I found a lower-bound on the decremental SSSP based on the online matrix vector hypothesis. Decremental SSSP is a dynamic version of SSSP where updates are edge-deletions. On the other hand, it is appearing clear to me, that typical conditional lower-bounds do not make sense for SSSP, since relevant conjectures show that the exponent can not be improved and do not exclude improvement of log factors. On the other hand, improving the exponent in SSSP means a sublinear algorithm which is excluded since the size of the input is a lower-bound on the running time of any problem.