News for hackers. Stuff that matters.

A comment on How Randomness Improves Algorithms?. Parent comment

Re:How Randomness Improves Algorithms? by lifeinthevoid on Saturday August 16, 2025 @01:42PM (#44925440)
> 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?

[ Parent | on HN ]
Re:How Randomness Improves Algorithms? by jvanderbot on Saturday August 16, 2025 @01:45PM (#44925471)
TFA (edit: in the politest way)
[ Parent | on HN ]
Re:How Randomness Improves Algorithms? by danhite on Sunday August 17, 2025 @07:19AM (#44930804)
>> 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...

[ Parent | on HN ]