Lower Bounds on Running time of Graph Algorithms
In the PRAM model without bit operations, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1]. 

Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See here, here, or the original paper for more details.

[1] Mulmuley, K. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput., 28(4), 1460–1509, 1999. (from author's webpage without paywall)