I agree with the thrust of the article but I want to quibble with one thing: the article says “calling RNGs that aren't seeded” doesn’t count as deterministic behavior, but randomized algorithms often have simpler implementations and better asymptotics than non-randomized algorithms while having statistical guarantees (“almost surely”) on their properties. Two of my favorite examples: (1) a randomized quicksort where choosing the pivot randomly in each iteration is simpler and better than deterministic methods of choosing the pivot; (2) a randomized treap gives you a balanced binary search tree with far simpler implementation than say a red black tree. And that’s besides the more utilitarian security benefit of using randomness inside hash functions so hash tables are resistant to HashDoS attacks.
So I’d implore the author to delete this restriction. Even when randomized algorithms produce different outputs (the treap giving you differently shaped trees with the same sequence of inserts) these outputs have properties that can be checked statistically.
great work the world needs more of this!
I agree with the thrust of the article but I want to quibble with one thing: the article says “calling RNGs that aren't seeded” doesn’t count as deterministic behavior, but randomized algorithms often have simpler implementations and better asymptotics than non-randomized algorithms while having statistical guarantees (“almost surely”) on their properties. Two of my favorite examples: (1) a randomized quicksort where choosing the pivot randomly in each iteration is simpler and better than deterministic methods of choosing the pivot; (2) a randomized treap gives you a balanced binary search tree with far simpler implementation than say a red black tree. And that’s besides the more utilitarian security benefit of using randomness inside hash functions so hash tables are resistant to HashDoS attacks.
So I’d implore the author to delete this restriction. Even when randomized algorithms produce different outputs (the treap giving you differently shaped trees with the same sequence of inserts) these outputs have properties that can be checked statistically.