[SEQ RERUN] Worse Than Random

The post isn't accurate. Randomness is viable when one is dealing with an actual adversary in the environment. In some sense the standard conjectures that P is equal to BPP) but that PP) is larger amounts to a set of conjectures saying that one can get some weak advantage from randomness. The context where one cannot get any advantage is where there's no active adversary , or where you care about average constraints rather than maximal constraints, which is only one set of contexts.

"Random" means, roughly, "independent of other stuff that might interact with what you're doing". When the environment providing that other stuff is simple, you can often do simple things that achieve that independence very effectively. When the environment is complicated, you may end up basically wanting to do something that has no simple patterns in it, which (depending on the definition of "simple") amounts to passing some randomness tests. When the environment is actively hostile, you want to be unpredictable by your adversary, which means having no patterns it can spot, and using a source of "real" randomness is a nice effective way to achieve that.

In the "easier" cases, indeed using a general-purpose thing-that-avoids-simple-patterns (i.e., something "random" in the usual sense) is an effective technique but something that takes more precise notice of the particular sorts of patterns you want to avoid can do better. In the "harder" cases, and especially those where you have an active, intelligent, adaptive adversary, it's entirely possible that randomness-as-usually-understood is the best practical solution.

As far as I can tell, this post is wrong as a matter of mathematical fact. There exist examples of problems in certain domains where a known randomized algorithm provably performs better than any deterministic algorithm.