Knuth Prize 2019 Awarded For Contributions To Complexity Theory |

Written by Sue Gee |

Sunday, 07 April 2019 |

Israeli mathematician and computer scientist, Avi Wigderson, who in addition to much original work in computation and complexity theory, has trained many generations of theoretical computer scientists through his visitor and postdoc program at the Institute for Advanced Study at Princeton, is this year’s recipient of the ACM/IEEE Donald E. Knuth Prize. Awarded by the ACM Special Interest Group on Algorithms and Computation Theory, this annual prize of $5,000, established in 1996, comes with a great deal of prestige and anyone in the Theoretical Computer Science community can nominate a candidate. The award is named after Donald Knuth of Stanford University who has been called the "father of the analysis of algorithms" and also dubbed the "Euclid of computer science" and awarded to individuals for contributions to the foundations of computer science. For 2019, the Knuth Prize committee, chaired by Avrim Blum, selected Avi Wigderson for his work in areas including randomized computation, cryptography, circuit complexity, proof complexity, parallel computation, and the understanding of fundamental graph properties. To quote from the citation:
The citation mentions co-authors of Wigderson's seminal papers in this field - Nisan in the case of “ His two landmark papers in cryptography, where he showed how one could compute any function securely in the presence of dishonest parties, were collaborations with Goldreich and Micali and with Ben-Or and Goldwasser respectively. The citation also notes:
Moving on to parallel computation Widgerson's foundational results about parallel computing models include, with Karp and Upfal, the first RNC algorithm for constructing a perfect matching in a graph and, with Karp, the first NC algorithm for finding a maximal independent set in a graph as well as a number of fundamental lower bound results. With regard to graph theory:
Wigderson's previous awards are, in 1994, the Nevanlinna Prize for his work on computational complexity and in 2009, along with Omer Reingold and Salil Vadhan, the Gödel Prize for work on the zig-zag product of graphs, a method of combining smaller graphs to produce larger ones used in the construction of expander graphs. He was elected to the National Academy of Sciences in 2013 and was elected as an ACM Fellow in 2018 for contributions to theoretical computer science and mathematics. By way of biographical details, according to Wikipedia Avi Wigderson was born in 1956 and graduated in 1980 from Technion in Haifa, Israel, and went on to Princeton University where his PhD in computational complexity was supervised by Richard Lipton, himself a winner of the Knuth Prize (2014) and also responsible for Widgerson's nomination. After short-term positions at the University of California, Berkeley, the IBM Almaden Research Centeri and the Mathematical Sciences Research Institute in Berkeley, he joined the faculty of Hebrew University in 1986. In 1999 he also took a position at the Institute for Advanced Study, and in 2003 he gave up his Hebrew University position to take up full-time residence at the IAS. If you are interested in a fuller account of Avi Wigderson's early life, his love of maths and his route into computer science watch the first few minutes of this interview with Alon Rosen from PCP Fest 2018: Asked about his childhood, Wigderson tells how his parents, originally from Poland, were holocaust survivors who arrived in Haifa in the early 1950s and brought up three sons in a one-bedroom apartment in a poor neighborhood that, as a child, he found idyllic. His father instilled in him a love or math which was fostered at school where he was inspired by a Russian emigre teacher who learned Hebrew from the boys he was instructing in math. The interview, which lasts over 100 minutes and which I haven't yet watched in its entirety, later goes into the subject matter indicated by its title - Complexity Theory and PCP. In its concluding minutes Wigderson talks about his love of teaching and lecturing and he also notes the value of randomness, one of the topics for which he is honored by the award of the Knuth Prize. ## More InformationSIGACT's long-form citation - Avi Wigderson ## Related ArticlesKnuth Prize 2018 Awarded For Contributions To Computational Complexity Goldwasser and Micali win Turing Award Knuth Prize 2011 Goes To Microsoft Researcher Donald Knuth & The Art of Computer Programming Donald Knuth At 80 Still Improving TAOCP Donald Knuth's Christmas Tree Lecture 2017 To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |

Last Updated ( Monday, 08 April 2019 ) |