Really interesting. I've often wondered this, but always thought that it would be too good to be true in most cases.
> But in two papers published in the 1990s, Wigderson and his collaborators proved that under certain assumptions, it’s always possible to convert a fast random algorithm into a fast deterministic algorithm. The result established that the complexity class known as “BPP” was exactly equal to the complexity class P. It tied decades of work on randomized algorithms neatly into the main body of complexity theory and changed the way computer scientists looked at random algorithms.
“I think that today almost anybody you asked would tell you randomness is weak rather than that randomness is powerful, because, under assumptions we strongly believe, randomness can be eliminated,” said Wigderson.
> But in two papers published in the 1990s, Wigderson and his collaborators proved that under certain assumptions, it’s always possible to convert a fast random algorithm into a fast deterministic algorithm. The result established that the complexity class known as “BPP” was exactly equal to the complexity class P.
What about those assumptions, though? Was progress made on those? Otherwise it is still unknown whether BPP = P or not. For the interested, it seems that the two publications are [1] and [2].
Lovasz is most well known to me for the Lovasz local lemma. Very cool to find out that this year’s Godel prize was given for an algorithmic construction for that.
> But in two papers published in the 1990s, Wigderson and his collaborators proved that under certain assumptions, it’s always possible to convert a fast random algorithm into a fast deterministic algorithm. The result established that the complexity class known as “BPP” was exactly equal to the complexity class P. It tied decades of work on randomized algorithms neatly into the main body of complexity theory and changed the way computer scientists looked at random algorithms.
“I think that today almost anybody you asked would tell you randomness is weak rather than that randomness is powerful, because, under assumptions we strongly believe, randomness can be eliminated,” said Wigderson.