It seems like there’s some word-trickery going on here. A randomized algorithm is just a deterministic algorithm plus a source of randomness, but the randomness source isn’t counted as an “input” but instead “part of the algorithm”. AMD is a situation where you want two copies of the same algorithm with the same inputs to have a different output, which is impossible. Using a “randomized” algorithm allows you to sneak around this limitation by giving each copy a possibly different input without calling it an input.
It seems like there’s some word-trickery going on here. A randomized algorithm is just a deterministic algorithm plus a source of randomness, but the randomness source isn’t counted as an “input” but instead “part of the algorithm”. AMD is a situation where you want two copies of the same algorithm with the same inputs to have a different output, which is impossible. Using a “randomized” algorithm allows you to sneak around this limitation by giving each copy a possibly different input without calling it an input.
Good point, but how is that a case of word-trickery, and what would you call this category of exception to the anti-randomness heuristic?