[qualudeheart]

Can the exponential probability increase mentioned by LeCun be mitigated, for example with an approximation?

Lots of algorithms like nearest neighbor search are O(n^2) but algorithms for approximate results run in sublinear time.