Knuth Prize to Avi Wigderson


Congratulations to the Knuth prize committee chaired by Avrim Blum for the excellent choice of awarding the 2019 Knuth prize to Avi Wigderson.

Avi has worked on all aspects of computational complexity theory, and he has had a transformative influence on the way theoretical computer science relates to pure mathematics. I will not repeat what I wrote about his work on the occasion of his 60th birthday here and here. Long-term readers of in theory will remember that I consider him as one of the saints of computational complexity.

The organizers of the coming FOCS would like me to remind you that the deadline is this Friday, and that someone, for some reason, has set up a fake submission site (on the domain aconf dot org) but the true submission site (that, to be honest, looks less legit than the fake one) is at

Also, the deadline to submit nominations for the inaugural FOCS test of time award is in three weeks. There will be three awards, one for papers appeared in FOCS 1985-89, one for FOCS 1995-99 and one for FOCS 2005-09.

On an unrelated note, GMW appeared in FOCS 1986 and the Nisan-Wigderson “Hardness versus randomness” paper appeared in FOCS 1988.


4 thoughts on “Knuth Prize to Avi Wigderson

  1. Pingback: Avi Wins The Knuth Prize | Gödel's Lost Letter and P=NP

  2. Pingback: Avi Wins The Knuth Prize - 2NYZ

  3. The P versus NP problem is a major unsolved problem in computer science. This is considered by many to be the most important open problem in the field. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. We prove the known NP-complete problem BETWEENNESS can be solved in polynomial time. We also provide a Computer Code and Software which decides the instances of this problem in polynomial time.

    The proof and code is in GitHub Inc:

    Thanks in advance!!!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s