Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How randomness improves algorithms (2023)

quantamagazine.org

Post reply on HN
Print view View original

21–24 of 24 posts

Re: How randomness improves algorithms (2023)

#21

Post by jvanderbot »

hinkley wrote: post #19
jvanderbot wrote: post #15

Earlier quoted context omitted.

Adversary input is basically at the core of analysis of these types of algorithms, yes. Here's another crossover analogy. In games, for any deterministic strategy there are games where you can't play a deterministic (pure) strategy and hope to get the best outcome, you need randomized (mixed) ones. Otherwise the Adversary could have anticipated and generated a different pathological response.

I think this started though with systems doing incremental work and then passing the result on to an algorithm that does worse with partially sorted or inverted lists than with random ones. Adversarial came later, particularly with the spread of the Internet.

I assure you adversarial analysis predates the internet

Re: How randomness improves algorithms (2023)

#22

Post by prerok »

jvanderbot wrote: post #11
pixelpoet wrote: post #7

Earlier quoted context omitted.

Guaranteed this is the case, I see it a lot too. They've done it twice before on previous submissions: https://news.ycombinator.com/item?id=44755116 and https://news.ycombinator.com/item?id=44785347 In case anyone is curious, the way to phrase it as a question would be, "How does randomness improve algorithms?"

Weirdly, "Why randomness improves Algorithms." Is closer to the truth and also cannot be expressed correctly with a question mark.

Indeed. Well, FWIW, the title translated into my native Slavic language would also make no sense with a question mark.

What's interesting is that both How... and How does... would translate into the same words but with a dot or a question mark at the end it would mean two different things.

That said, that would be true for many languages.

Re: How randomness improves algorithms (2023)

#23

Post by danhite »

lifeinthevoid wrote: post #16
jvanderbot wrote: post #13

Earlier quoted context omitted.

Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one. So its not going do the kind of game changing class breaking work you're looking for. You know, where random is the only way. How randomization helps is by making it much easier to design algorithms. E.g. Verifying a solution is cheap, so proving your random choice is in some class of good choices and making an algorithm t…

> Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one Oh, that's cool, do you have a reference for that?

>> Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one > Oh, that's cool, do you have a reference for that?

The OP article has such a reference, but theirs is paywalled, and perhaps you missed it, so you may wish to see this no paywall link to the paper:

Hardness vs. Randomness by Noam Nisan & Avi Wigderson https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HAR...

Re: How randomness improves algorithms (2023)

#24

Post by jvanderbot »

furyofantares wrote: post #20
jvanderbot wrote: post #13

Earlier quoted context omitted.

Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one. So its not going do the kind of game changing class breaking work you're looking for. You know, where random is the only way. How randomization helps is by making it much easier to design algorithms. E.g. Verifying a solution is cheap, so proving your random choice is in some class of good choices and making an algorithm t…

I'm not looking for any kind of game changing class breaking work. I don't think I'm being understood here at all. I must have put too much emphasis on PRNG or on maybe there's a more intelligent way to sample - you can ignore those comments. I just think it's framed poorly to make it sound more counterintuitive than it is.

It happens. Sorry for misunderstanding
Post reply on HN