An example of a new breakthrough doesn't directly apply but conceptually it shows how a large NP space can be reduced to P by using localized randomness to act as a proxy for the large search space.
That's a great, great invention, it allows an beautiful dance between exponent and double exponent. I was aware of it almost from beginning and was shocked by lack of coverage of this event. Well, NP barrier stays, but now we have a great tool to punch some holes 
EDIT: Try to not think about it as of randomness
