How randomness can improve algorithms

https://www.quantamagazine.org/how-randomness-improves-algorithms-20230403/

by nsoonhui • 3 years ago

65 26 3 years ago

vlovich123• 3 years ago

Semi related, hashing can also improve algorithms that need to evenly distribute load without actually needing any load balancer (provided on average the work per request is roughly equal). Kind of random since good hash algorithms are non reversible and distribute the bits evenly across the space.

chriswarbo• 3 years ago

Hashing is also deterministic, which can be useful for reproducibility. Cryptographic hashing is also a demonstration of "nothing up my sleeve". I've used this in benchmarks, where "random" choices in input selection are derived from cryptographic hashes of the inputs; so (a) anybody can reproduce a previous result, (b) every update will cause completely different selections to be made, and (c) it's difficult to force that selection into something that favours one or another system.

schuyler2d• 3 years ago

Is this roughly saying that when a random choice is more likely to be close to an ideal median (e.g. the center-ish edge in a graph) than the effort in finding a median choice (e.g. determining which edges are in the "center" of a graph), then use randomness?

dellamonica• 3 years ago

There are lots of techniques that use randomness to show the existence of objects with desired properties. Some of them rely on the "first moment" (expectation) which seems to be what you are saying. These tend to be the simpler ones.

A good book on the topic is The Probabilistic Method by Alon and Spencer.

To give you some hint of what randomness can get you, look at the most typical random graph model, which for a probability p selects an edge uniformly and independently with that prob. With overwhelming probability, this graph is extremely uniform, meaning that in every set you look (other than then very tiny ones) the density of edges is very close to p. Actually constructing such a graph, either symbolically or by an algorithm is a very hard problem and even the best known results don't get us close to the real random model.

thehumanmeat• 3 years ago

I also have two blog posts on this topic!

https://treymanuszak.eth.limo/blog/power-of-randomness https://treymanuszak.eth.limo/blog/yao-minimax

notduncansmith• 3 years ago

This snippet from the article:

In 1994, the computer scientists Noam Nisan and Avi Wigderson helped resolve this confusion by demonstrating that randomness, though useful, probably isn’t necessary. They proved that one of two things must be true: Either all problems that can be efficiently solved using randomness also have fast deterministic algorithms, or many notoriously difficult problems are secretly easy. Computer scientists consider the second possibility very unlikely.

Reminds me of the popular hacker koan:

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6. "What are you doing?" asked Minsky. "I am training a randomly wired neural net to play tic-tac-toe," Sussman replied. "Why is the net wired randomly?" asked Minsky. Sussman replied, "I do not want it to have any preconceptions of how to play." Minsky then shut his eyes. "Why do you close your eyes?" Sussman asked his teacher. "So that the room will be empty," replied Minsky. At that moment, Sussman was enlightened.

smeagull• 3 years ago

Pseudorandom generators are deterministic. Job done. Turing award please.

OscarCunningham• 3 years ago

Of course the challenge is proving that good enough pseudorandom generators actually exist.

bodhiandphysics3• 3 years ago

It's a little funny for me to say this (my shtick in my lab is that I used randomized algorithms for everything), but whether this is true is actually a major open problem in complexity theory. Many famous problems are polynomial using random algorithms (famously determining if a number is Prime, and min cut of a graph), but over the years poly time algorithms have been found for many of these situations. Most complexity theorists I find believe that the random complexity classes (ZPP, RP, and BPP) are probably just P (BQP, the quantum analog to BPP is almost certainly not P). That of course doesn't mean that randomization can't speed you up! Prime determination is O(n^6) deterministically but O(n^2) using random search, n being the number of bits.

Ar-Curunir2• 3 years ago

yup. To elaborate (informally) on why theorists believe BPP = P, basically if we believe cryptography and hence PRGs exist, then every algorithm can be derandomized.

adgjlsfhk1• 3 years ago

How does this follow? I understand that PRNGs let you construct randomized algorithms in practice, but how do you transfer probably polynomial runtime to definitely polynomial runtime?

ablob• 3 years ago

How does PRNG follow from cryptography?

forty• 3 years ago

This a a good summary of the article ^^

mycall• 3 years ago

How can you improve a binary search using randomness?

zuminator• 3 years ago

I was surprised there was no mention of the now-ubiquitous generative models for AI image creation, as it's a textbook example of results being drastically improved by the utilization of pseudorandom noise.

friend_and_foe• 3 years ago

I love stuff like this, it's a strong personal interest of mine.

For some of you information theory buffs out there, is it fair to say that a probabilistic algorithm is a heuristic? Is the inverse true, are all heuristics some type of probabilistic algorithm when simplified and generalized?

If a randomness extractor can deliver uniformly random output from a weakly random entropy source, is there some function by which a signal or pattern can be extracted from a weakly random source?

williamkuszmaul• 3 years ago

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.

unlikelymordant• 3 years ago

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.

How randomness can improve algorithms

Related Stories