TMCnet News
AVI WIGDERSON RECEIVES ACM A.M. TURING AWARD FOR GROUNDBREAKING INSIGHTS ON RANDOMNESSLeading Theoretical Computer Scientist Cited for Field-Defining Contributions NEW YORK, April 10, 2024 /PRNewswire/ -- ACM, the Association for Computing Machinery, today named Avi Wigderson as recipient of the 2023 ACM A.M. Turing Award for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science. The ACM A.M. Turing Award, often referred to as the "Nobel Prize of Computing," carries a $1 million prize. Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey. He has been a leading figure in areas including computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computation, combinatorics, and graph theory, as well as connections between theoretical computer science and mathematics and science. The ACM A.M. Turing Award, often referred to as the "Nobel Prize of Computing," carries a $1 million prize with financial support provided by Google, Inc. The award is named for Alan M. Turing, the British mathematician who articulated the mathematical foundations of computing. What is Theoretical Computer Science? Theoretical computer science also explores the design of efficient algorithms. Every computing technology that touches our lives is made possible by algorithms. Understanding the principles that make for powerful and efficient algorithms deepens our understanding not only of computer science, but also the laws of nature. While theoretical computer science is known as a field that presents exciting intellectual challenges and is often not directly concerned with improving the practical applications of computing, research breakthroughs in this discipline have led to advances in almost every area of the field—from cryptography and computational biology to network design, machine learning, and quantum computing. Why is Randomness Important? These, and many other fundamental questions lie at the heart of understanding randomness and pseudorandomness in computation. An improved understanding of the dynamics of randomness in computation can lead us to develop better algorithms as well as deepen our understanding of the nature of computation itself. Wigderson's Contributions Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of workson trading hardness for randomness. They proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently derandomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness. This series of influential papers include the following three:
Importantly, the impact of these three papers by Wigderson goes far beyond the areas of randomness and derandomization. Ideas from these papers were subsequently used in many areas of theoretical computer science and led to impactful papers by several leading figures in the field. Still working within the broad area of randomness in computation, in papers with Omer Reingold, Salil Vadhan, and Michael Capalbo, Wigderson gave the first efficient combinatorial constructions of expander graphs, which are sparse graphs that have strong connectivity properties. They have many important applications in both mathematics and theoretical computer science. Outside of his work in randomness, Wigderson has been an intellectual leader in several other areas of theoretical computer science, including multi-prover interactive proofs, cryptography, and circuit complexity. Mentoring "It's important to point out that Avi Wigderson also received the Abel Prize, which is considered the most important honor for lifetime achievements in the field of mathematics," explained ACM President Yannis Ioannidis. "Being selected for the ACM A.M. Turing Award is a fitting follow-up—as mathematics is foundational to computer science and Wigderson's work has connected a wide range of mathematical sub-areas to theoretical computer science. Wigderson is a towering intellectual force in theoretical computer science, an exciting discipline that attracts some of the most promising young researchers to work on the most difficult challenges. This year's Turing Award recognizes Wigderson's specific work on randomness, as well as the indirect but substantial impact he has had on the entire field of theoretical computer science." "Avi Wigderson's work on randomness and other topics has set the agenda in theoretical computer science for the past three decades," explained Jeff Dean, Senior Vice President, Google. "From the earliest days of computer science, researchers have recognized that incorporating randomness was a way to design faster algorithms for a wide range of applications. Efforts to better understand randomness continue to yield important benefits to our field, and Wigderson has opened new horizons in this area. Google also salutes Wigderson's role as a mentor. His colleagues credit him with generating great ideas and research directions, and then motivating a new generation of smart young researchers to work on them. We congratulate Avi Wigderson on receiving the ACM A.M. Turing Award—computing's highest honor." Biographical Background A graduate of The Technion – Israel Institute of Technology, Wigderson earned MA, MSE, and PhD degrees in Computer Science from Princeton University. Wigderson's honors include the Abel Prize, the IMU Abacus Medal (previously known as the Nevanlinna Prize), the Donald E. Knuth Prize, the Edsger W. Dijkstra Prize in Distributed Computing, and the Gödel Prize. He is an ACM Fellow and a member of the U.S. National Academy of Sciences and the American Academy of Arts and Sciences. About the ACM A.M. Turing Award About ACM View original content to download multimedia:https://www.prnewswire.com/news-releases/avi-wigderson-receives-acm-am-turing-award-for-groundbreaking-insights-on-randomness-302112320.html SOURCE Association For Computing Machinery, Inc. |