Re:How Randomness Improves Algorithms?
by furyofantares on Saturday August 16, 2025 @02:21PM
(#44925739)
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.
Re:How Randomness Improves Algorithms?
by jvanderbot on Sunday August 17, 2025 @01:03PM
(#44933069)
It happens. Sorry for misunderstanding
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?
Re:How Randomness Improves Algorithms?
by jvanderbot on Saturday August 16, 2025 @01:45PM
(#44925471)
TFA (edit: in the politest way)
>> 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...
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 that turns that into a solution is still an interesting approach and opens up solutions to things we cant yet solve.
Derandomizing as presented apparently means proving for a few random but careful choices you're in the funnel towards the right solution, or (hopefully) can detect otherwise, and a few transformations or reasonably performant steps produce your solution.