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:

Wigderson’s work revolutionized our understanding of randomness in computation. In a series of results, he showed under widely-believed computational assumptions that every probabilistic polynomial time algorithm can be fully derandomized. In other words, randomness is not necessary for polynomial-time computation.

The citation mentions co-authors of Wigderson's seminal papers in this field - Nisan in the case of “Hardness vs. Randomness”; Babai, Fortnow and Nisan for “BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs” and Impagliazzo for “P=BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”. It also note that this last-mentioned paper, which showed that P=BPP is implied by the assumption that there exist functions that can be computed by exponential-time Turing machines that cannot be computed by subexponential-size circuits in the worst case, is one of the strongest pieces of evidence we have that P = BPP.

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:

Additionally, originating from cryptography but with applications to many areas in theoretical computer science, Wigderson with Ben-Or, Goldwasser, and Kilian defined the model of multiprover interactive proofs. This model for the first time showed how it would be possible for a polynomialtime machine to verify an exponentially-long proof. This idea had substantial impact, and among other things it led to the celebrated PCP theorem and the flow of follow-up works on hardness of approximation

Moving on to parallel computation Wigderson'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:

With Reingold, Vadhan and Capalbo, Wigderson gave the first efficient combinatorial constructions of expander graphs, an important class of highly connected sparse graphs. Before this work, only algebraic constructions had been known. Wigderson’s development of combinatorial expander constructions enabled a series of important subsequent results including Reingold’s deterministic logspace algorithm for st-connectivity. 

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 Wigderson'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 Information

SIGACT's long-form citation - Avi Wigderson

Knuth Prize

Avi Wigderson - Wikipedia

Related Articles

Knuth 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

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info