Avi Wigderson and László Lovász Win the Abel Prize
quantamagazine.org
quantamagazine.org
> 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.
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].