How randomness can improve algorithms | Hacker News Reader

How randomness can improve algorithms

quantamagazine.org

65 pointsnsoonhui26 comments

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.

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.

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?

If you can make pseudorandom numbers well enough deterministically in polynomial time, you can simulate any algorithm in BPP in polynomial time on a deterministic turing machine, so BPP = P

Can you recommend an accessible proof for this? (is this simply because if the error probability is too low, it must be zero?)

Are there problems in BPP that can defend against "helping" PRNGs by diagonalizing against them somehow?

A BPP algorithm can be seen as a deterministic algorithm that takes a string of random bits as part of its input. One way to derandomize a BPP algorithm is to run it with every possible random string and pick the answer that the majority of random strings lead to. This blows up the running time by 2^r with r being the length of the random string, making the running time exponential.

If the PRNG can take a seed of length log(n) and generate a random string from it, then you might try to take a BBP algorithm and reduce the length of the random input to log(n) using the PRNG. We assume that the PRNG being good enough means that this new algorithm still has the usual BBP guarantee that it gives the correct answer for at least 2/3 of the seeds.

However, now the derandomization of running it on every possible seed just gives a slowdown of 2^log(n) = n, which means that the running time stays polynomial.

Cannot you get extremely unlucky so that for one input all the PRNG seeds map into a subset of the 1/3 unhelpful random strings?

It's not "probably polynomial time", it's polynomial time with bounded error probability. Derandomization means bringing the probability to 0.

The definition of a PRNG in complexity theory (for the purposes of this topic) is that no polynomial-time algorithm can look at its output and distinguish it from real randomness (with high confidence etc etc).

Now imagine you have a PRNG whose seed size is logarithmic in the output size. You can compose it with our BPP algorithm and iterate over all the possible seeds in polynomial time (because the seed is logarithmic), and take the majority result. You built a polynomial time algorithm that, if it gave incorrect results, could distinguish the PRNG from real randomness. So it must be correct.

it can be probably polynomial time... that's ZPP! (ZPP is the complexity class of languages that are accepted by a randomized turing machine in expected polynomial time. However, in the worst case, the turing machine is allowed to take arbitrary time). In ZPP note the error probability is 0... it always returns YES or NO correctly.

It's unknown whether ZPP = P (but it almost certainly does). It is known that ZPP is the base of the random hierarchy... ZPP = RP u co-RP, where RP is the class of languages that are accepted with bounded error.

Any good complexity textbook beyond Sipser will discuss the randomized complexity classes at extreme detail, since they are crucial for constructing all the other interesting complexity classes (notably IP and MIP).

Sure, there are plenty of complexity classes :) but TFA is about derandomization of BPP, even if it doesn't mention the class by name, it talks about Nisan-Widgerson.

How does PRNG follow from cryptography?

The cryptographic definition of a PRNG is an algorithm whose output is indistinguishable from true randomness by any polynomial-time process. You can think of a BPP algorithm A as a deterministic one that takes randomness as an additional input. If the PRNG is truly a PRNG, then one can replace this random input to A with the output of a PRNG, and the output of A can't change.

This a a good summary of the article ^^

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.

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

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

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.

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.

I also have two blog posts on this topic!

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

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.

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.

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?

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.

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?

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.

How can you improve a binary search using randomness?

Reply on news.ycombinator.com