Avi Wigderson and László Lovász Win the Abel Prize(quantamagazine.org)
quantamagazine.org
Avi Wigderson and László Lovász Win the Abel Prize
https://www.quantamagazine.org/avi-wigderson-and-laszlo-lovasz-win-abel-prize-20210317/
7 comments
> 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].
[1] https://doi.org/10.1007%2Fbf01275486
[2] https://doi.org/10.1145%2F258533.258590
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].
[1] https://doi.org/10.1007%2Fbf01275486
[2] https://doi.org/10.1145%2F258533.258590
I believe the assumption is essentially that PRNGs (pseudo random number generators) exist.
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.