Provable Lower Bounds for some Algorithmic Problems? Are there any problems for which we have known lower bounds?
For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons.
Edit: I'm aware that this requires restricting the algorithm to comparisons. I couldn't think of any lower bound in an unrestricted model, but I'm mostly interested in lower bounds for unrestricted computations.
My motivation for this is: while we don't know how to prove that one-way functions exist, maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key.
Does this question make sense? If not, where do I go amiss? Do my calculations make any sense?
maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it

Even that limited goal is beyond what we can prove.  People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was surprisingly small.  One would hope that the difference becomes wider once the size of the function increases; however we can't prove it.

Does this question make sense?

Yes, it does (although, depending on how you define things, the $c \cdot 319557$ may be the time required to evaluate in the forward direction, rather than the number of bits); we just don't know the answer.
Now, the obvious question may be, if we can prove that comparison based sorting takes $\Omega(n \log n)$ operations, why can't we do anything analogous with inverting functions?  Well, with the comparison based sorting proof, the only information we allow the sorting algorithm about the relative order of elements is to call the Oracle, which returns a single bit each time.  And, we can prove that any sorting algorithm with that restriction must call the Oracle $\Omega(n \log n)$ times (because it needs to distinguish between $n!$ different sort orders), and hence must take at least $\Omega(n \log n)$ time.  However, that proof is valid only if we restrict the program in that way; sorting algorithms that don't abide by that restriction (e.g. radix sorting or interpolation sorting) can go faster.  And (the point I'm really trying to make) when we ask for a function to be inverted by any means, we don't require the program to use any sort of Oracle to get the information we need, hence the type of proof we used for comparison based sorting doesn't work.