[HN Gopher] Avi Wigderson and Laszlo Lovasz Win the Abel Prize
       ___________________________________________________________________
        
       Avi Wigderson and Laszlo Lovasz Win the Abel Prize
        
       Author : digital55
       Score  : 45 points
       Date   : 2021-03-17 11:09 UTC (11 hours ago)
        
 (HTM) web link (www.quantamagazine.org)
 (TXT) w3m dump (www.quantamagazine.org)
        
       | singhrac wrote:
       | 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.
        
         | hanche wrote:
         | As far as I know, this year's Godel prize is not yet awarded.
         | The current story is about the Abel prize.
        
           | singhrac wrote:
           | Ah sorry, I know that. I meant the 2020 Godel prize awarded
           | to Moser and Tardos. Just noting the connection.
        
       | blackbear_ wrote:
       | > 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
        
       | karmakaze wrote:
       | 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.
        
       ___________________________________________________________________
       (page generated 2021-03-17 23:03 UTC)