Can the exponential probability increase mentioned by LeCun be mitigated, for example with an approximation? Lots of algorithms like nearest neighbor search ar

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.