Randomness Improves Algorithms

Re:Randomness Improves Algorithms by williamkuszmaul on Wednesday April 05, 2023 @08:42AM (#35453161)

One important caveat: it is widely believed that randomization does make a big difference for data structures problems. For example hash tables (which use random hash functions) take O(1) time per operation, but it is conjectured that no deterministic data structure can match this.

There are also problems in online algorithms where randomization provably changes what is possible, for example the "cup game problem." (https://arxiv.org/abs/1904.02861)

Finally, although randomized primality testing (1970s) is often credited as the start of randomized algorithms as a field, it's worth noting that hash tables (1954) and quick sort (1961) were much earlier.

[ Parent | on HN ]

Re:Randomness Improves Algorithms by unlikelymordant on Wednesday April 05, 2023 @09:16AM (#35453623)

are hash functions considered random? considering they are deterministic in their inputs and outputs. With randomised primality testing, you could use a true random number (based on e.g. nuclear decay) every time, and get the same correctness guarantees. With a hash table, you could never retrieve anything if you always used a true random number as a key every time.

[ Parent | on HN ]