Examples of the price of abstraction? Theoretical computer science has provided some examples of "the price of abstraction."  The two most prominent are for Gaussian elimination and sorting.  Namely:


It is known that Gaussian elimination is optimal for, say, computing the determinant if you restrict operations to rows and columns as a whole [1].  Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.
In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard $n \log n$ information-theoretic lower bound.  Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.



  Are there other examples of the price of abstraction?


To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model.  Furthermore, the weakness of the weak model should come in the form of an abstraction, which admittedly is a subjective notion.  For example, I do not consider the restriction to monotone circuits to be an abstraction.  Hopefully the two examples above make clear what I'm looking for.

[1]  KLYUYEV, V.V., and N. I. KOKOVKIN-SHcHERBAK: On the minimization of the
number of arithmetic operations for the solution of linear algebraic systems of
equations. Translation by G. I. TEE: Technical Report CS 24, June t4, t965,
Computer Science Dept., Stanford University.
Another beautiful example of the price of abstraction: network coding. It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place.