The best class of algorithms in this category are those where you know for certain that one answer is impossible and the other is highly probable. Like Bloom Filters, and if you squint, consistent hashing. I wish we had more algorithms of this sort and books about them. If I were a professor I’d be tempted to propose teaching a class.

When I was just starting out, client-server was still a bit of a specialty, mostly reserved for gaming and large institutions. Most of my education was in single task computing. If the university hadn’t offered a class in distributed computing I wouldn’t have gotten much in that direction except in independent study.

In the time since then, we seem to have focused much less on seconds per task and more on tasks per second, which results in more concern about statistical spreads, and queuing mechanisms to manage the variability between a hit and a miss. It would be better if this sort of computation were more organized into a discipline.

My personal favourite is compressive sensing, sparse signals beat the Nyquist sampling limit, by what seems like an unbounded amount 1000x, 1000000x, etc, because all real world stuff we care about lives on a low dimensional manifold, so unlike the noise.

Sampling above the nyquist sampling limit then representing it as something else is not beating the nyquist sampling limit, it's just compression.

You mean below, not above?

It's not compression. Look it up, it's really cool. Random sampling in a sparse basis. Single pixel camera can reconstruct a 10MP image, etc.

You may enjoy randomised algorithms (https://www.cl.cam.ac.uk/teaching/2425/RandAlgthm/)

The entire field of operations research is essentially founded on the premise that NP hard is just a starting place.

If anything, NP hard problems are usually the ones worth tackling.