News for hackers. Stuff that matters.
Re:How Randomness Improves Algorithms? by jvanderbot on Saturday August 16, 2025 @01:23PM (#44925316)
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 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.

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)
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...