The 2023 winner of the Turing Award, known as the 'Nobel Prize of computer science,' has been selected as Avi Vigderson for his contributions to understanding randomness in computation.

by Institute for Advanced Study

Avi Vigderson, a computer scientist from the Institute for Advanced Study in Princeton , Israel, has been selected as the 2023 recipient of the Turing Award , which is given to individuals who have made outstanding contributions to computer science. Vigderson is recognized for 'reshaping our understanding of randomness in computation' and for 'decades of intellectual leadership in theoretical computer science.'

2023 Turing Award
https://awards.acm.org/about/2023-turing

Graduate Avi Wigderson wins Turing Award for 'groundbreaking insights' in computer science
https://www.princeton.edu/news/2024/04/10/grad-alum-avi-wigderson-wins-turing-award-groundbreaking-insights-computer-science

Computer scientist wins Turing Award for seminal work on randomness | Ars Technica
https://arstechnica.com/science/2024/04/computer-scientist-wins-turing-award-for-seminal-work-on-randomness/

For Turing Award winner, everything is computational and some problems are unsolvable | ZDNET
https://www.zdnet.com/article/for-turing-award-winner-everything-is-computation-and-some-problems-are-unsolvable/

The Association for Computing Machinery (ACM), an international academic society in the field of computer science, has decided to award the 2023 Turing Award to Vigderson of Princeton Laboratory on April 10, 2024. The Turing Award is named after Alan Turing , who made important contributions to the dawn of electronic computing, and is a prestigious award also known as the 'Nobel Prize of computer science.' The winner will receive $1 million (approximately 150 million yen) with the support of Google.

Vigderson was born in Haifa , Israel in 1956, the son of an electronics engineer and a nurse. After earning a bachelor's degree from the Technion, Vigderson went on to Princeton University in the United States and earned a PhD in computer science in 1983. At the time of writing, he is a professor of mathematics at the Institute for Advanced Study in Princeton.

'Computation is a really fundamental concept. Not just computer algorithms, everything computes,' Vigderson said in an interview with ZDNet, arguing that a wide range of phenomena, from the patterns on seashells to the development of embryos, the construction of termite mounds by termites, and even the spread of gossip, are computations. 'How information evolves, whether it's when you're being taught something by someone or when you talk about something you saw on Facebook, is a computational problem that can be built with a complete computational model,' he said.

One of the reasons Vigderson was awarded the Turing Award is that he reconstructed our understanding of randomness in computer calculations. Although computers are fundamentally deterministic systems, researchers in the 1970s discovered that by deliberately making random choices during a calculation, they could ultimately improve the efficiency of the algorithm. Therefore, computer scientists started with a randomized version of a deterministic algorithm (a probabilistic algorithm) and then derandomized it to obtain a deterministic algorithm.

However, in a 1994 paper , Vigderson proved that any efficient probabilistic algorithm can be replaced by a deterministic one, and that efficient computation does not require randomness. In two subsequent papers , he expanded on his work on randomness.

'The question was, how strong is the randomness of the algorithm? These papers were intended to show that the randomness is not that strong,' Vigderson said. 'They all take a hard problem and make a pseudorandom generator that deterministically produces random-looking bits, and then replace the random input of a probabilistic algorithm to make it deterministic.'

The ideas in these papers have had a major impact on the field of theoretical computer science, and are being used by applied researchers in real-world software. ACM praised the paper, stating, 'This body of work has revolutionized the role of randomness in computation and our understanding of what randomness is.'

In addition to his groundbreaking technical contributions, Vigderson is also respected as a mentor to many young researchers. 'His vast knowledge and unparalleled technical proficiency, combined with his friendliness, enthusiasm and generosity, have attracted many of the best young people to pursue careers in theoretical computer science,' ACM said in a statement.