Thursday, December 31, 2020

Complexity Year in Review 2020

For the result of the year we go to all the way back to the "before times".
MIP*=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen
A follow up to last year's runner up NEEXP in MIP*, the new paper shows how to prove everything computable and beyond to a polytime verifier with two provers who cannot communicate but share entangled quantum bits. The result had a bit of a scare but fixed up this fall.

Honorary mention goes to beating the Christofides-Serdyukov approximation for traveling salesman by Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan. Nathan got his start in Bill's REU program.

Of course when we think back at 2020 it won't be the theorems but the pandemic, a divisive election and racial reckoning. The word of the year for academia is "virtual", virtual teaching, virtual research collaborations, virtual talks, virtual conferences, virtual panels and virtual job visits. For the most part the the pandemic hasn't really created new trends but accelerated trends already in place. Given the far lower costs in terms of time, money and the environment, how much of "virtual" will remain post-corona?

Bill's published a new book on muffin problems, his second book in two years. I started a new College of Computing

In 2021 we will likely see the end of the pandemic and most definitely see the 50th anniversary of P versus NP. Hope for a successful and healthy year for all. 


  1. Why don't you list the new book on the left with the other two?
    Typo in first line: they -> the

    1. Fixed typo. Thanks.

      Every time you visit this blog, one of Bill's books is randomly chosen to be displayed on the left.