https://awards.acm.org/about/2023-turing skip to main content * ACM Home * ACM A.M. Turing Award * Turing 50 * Digital Library * CACM * Queue * TechNews ACM Logo ACM Logo ACM recognizes excellence * Home * Award Recipients * Contact Us * Search Input [ ] Search Submit [Search] * Home Award Recipients Contact Us Search [ ] * ACM Awards + Awards Home o Spotlight on Turing Laureates o ACM A.M. Turing Award o ACM Prize in Computing o ACM Charles P. "Chuck" Thacker Breakthrough in Computing Award o ACM Distinguished Service Award o ACM Doctoral Dissertation Award o ACM-IEEE CS Eckert-Mauchly Award o ACM Frances E. Allen Award o ACM Grace Murray Hopper Award o ACM Gordon Bell Prize o ACM Gordon Bell Prize for Climate Modelling o International Science and Engineering Fair o ACM Paris Kanellakis Theory and Practice Award o ACM Karl V. Karlstrom Outstanding Educator Award o ACM-IEEE CS Ken Kennedy Award o ACM Eugene L. Lawler Award o ACM-IEEE CS George Michael Memorial HPC Fellowships o ACM AAAI Allen Newell Award o Outstanding Contribution to ACM Award o ACM Policy Award o ACM Presidential Award o SIAM/ACM Prize in Computational Science and Engineering o ACM Software System Award o ACM Athena Lecturer Award o ACM India Doctoral Dissertation Award o ACM/CSTA Cutler-Bell Prize for High School Computing o Sponsors of ACM Awards + About ACM Awards Giving Credit where Credit Is Due ACM recognizes excellence through its eminent awards for technical and professional achievements and contributions in computer science and information technology. It also names as Fellows and Distinguished Members those members who, in addition to professional accomplishments, have made significant contributions to ACM's mission. ACM awards recognize achievements by young computing professionals, educators, theoretical computer scientists, software systems innovators, and pioneers who have made humanitarian and cross-discipline contributions. + 2023 ACM A.M. Turing Award recipient Avi Wigderson ACM Announces 2023 A.M. Turing Award Recipient acm-fellows-member-badge.jpg ACM Names 2023 Fellows acm-distinguished-member-badge.jpg ACM Names 2023 Distinguished Members * Advanced Member Grades + Advanced Grades of Membership o ACM Fellows o ACM Distinguished Members o ACM Senior Members o ACM Fellows FAQ o ACM Distinguished Members FAQ o ACM Senior Members FAQ o ACM Fellows Committee o ACM Distinguished Member Committee + ACM Advanced Grades of Membership The ACM Advanced Grades of Membership program recognizes the achievements of ACM members through all stages of their career. + acm-fellows-member-badge.jpg ACM Names 2023 Fellows acm-distinguished-member-badge.jpg ACM Names 2023 Distinguished Members * SIG Awards + About SIG Awards o SIGACCESS o SIGACT o SIGAda o SIGAI o SIGAPP o SIGARCH o SIGBED o SIGBio o SIGCAS o SIGCHI o SIGCOMM o SIGCSE o SIGDA o SIGDOC o SIGEcom o SIGEVO o SIGIR o SIGGRAPH o SIGHPC o SIGKDD o SIGLOG o SIGMETRICS o SIGMICRO o SIGMIS o SIGMM o SIGMOBILE o SIGMOD o SIGOPS o SIGPLAN o SIGSAC o SIGSAM o SIGSIM o SIGSOFT o SIGUCCS o SIGWEB + About SIG Awards ACM's Special Interest Groups (SIGs) regularly cite outstanding individuals for their contributions in more than 30 distinct technological fields. + * Regional Awards + About Regional Awards o ACM India Doctoral Dissertation o ACM India Early Career Researcher o ACM India Outstanding Contributions in Computing by a Woman o ACM India Outstanding Contribution to Computing Education o IPSJ/ACM Award for Early Career Contributions to Global Research o CCF-ACM Award for Artificial Intelligence + About ACM Regional Awards ACM recognizes the contributions of individuals working primarily within specific regions of the world through awards given by its regional councils, and through partnerships with international societies. + siddharth-barman.jpg ACM India ECR 2023 Award nutan-limaye.jpg ACM India OCCW 2023 Award OCCE 2023 award recipient Sudip Misra ACM India OCCE 2023 Award * Nominations + Award Nominations o ACM A.M. Turing Award o ACM Prize in Computing o ACM Charles P. "Chuck" Thacker Breakthrough in Computing Award o ACM Frances E. Allen Award o ACM Distinguished Service Award o ACM Doctoral Dissertation Award o ACM-IEEE CS Eckert-Mauchly Award o ACM Gordon Bell Prize o ACM Grace Murray Hopper Award o ACM Paris Kanellakis Theory and Practice Award o ACM Karl V. Karlstrom Outstanding Educator Award o ACM-IEEE CS Ken Kennedy Award o ACM Eugene L. Lawler Award o ACM-IEEE CS George Michael Memorial HPC Fellowships o Outstanding Contribution to ACM Award o ACM AAAI Allen Newell Award o ACM Policy Award o SIAM/ACM Prize in Computational Science and Engineering o ACM Software System Award o ACM Athena Lecturer Award o ACM/CSTA Cutler-Bell Prize in High School Computing o ACM Fellows o ACM Distinguished Members o ACM Senior Members + Awards Nominating Process How to Nominate Award nominations deadlines occur throughout the year, with a heavy concentration in January. Please refer to the Nomination Process page for each award, which includes not only information about the deadline but also guidance for preparing each type of nomination. ACM's conflict-of-interest guidelines apply to all award nominations. + [athena-lec] Call for Nominations og-awards.jpg ACM Honors & Ethics * Honors and Ethics + Policy for Honors Conferred by ACM o Policies and Procedures for Honors Conferred by ACM + ACM Honors and Ethics ACM formally recognizes individuals for significant contributions to the field, ACM, or its interests. ACM expects individuals it honors to abide by the ACM Code of Ethics and Professional Conduct. Learn about ACM's policies and procedures for integrating expectations of ethical behaviour and ACM Awards. + [athena-lec] Call for Nominations og-awards.jpg ACM Honors & Ethics * Awards Committees + ACM Awards Committee o ACM A.M. Turing Award Committee o ACM Prize in Computing Committee o ACM Charles P. "Chuck" Thacker Breakthrough in Computing Committee o ACM Frances E. Allen Award o ACM Distinguished Service Award Committee o ACM Doctoral Dissertation Award Committee o ACM-IEEE CS Eckert Mauchley Award Committee o ACM Gordon Bell Prize Committee o ACM Grace Murray Hopper Award Committee o ACM Paris Kanellakis Theory and Practice Award Committee o ACM Karl V. Karlstrom Outstanding Educator Award Committee o ACM-IEEE CS Ken Kennedy Award Committee o ACM Eugene L. Lawler Award Committee o ACM-IEEE CS George Michael Memorial HPC Fellowships Committee o ACM AAAI Allen Newell Award Committee o Outstanding Contribution to ACM Award Committee o ACM Policy Award Committee o SIAM/ACM Prize in Computational Science and Engineering Committee o ACM Software System Award Committee o ACM Athena Lecturer Award Committee o ACM India Doctoral Dissertation Award Committee o ACM Fellows Committee o ACM Distinguished Member Committee o ACM Senior Member Committee o Conflict of Interest Guidelines + About ACM Awards Committees At the core of the ACM Awards program is a dedicated group of volunteers who serve on the committees of the ACM Awards to recognize individuals for their excellence in the computing fields + awards-ctte-co-chairs.jpg * Establishing an Award + Policies and Guide for Establishing an ACM Award o ACM Publications Board Guidelines for Establishing a Best Paper Award for ACM Periodicals + Policies and Guide ACM welcomes proposals for the establishment of new awards, to recognize contributions based on merit, service, or for an outstanding paper. + [athena-lec] Call for Nominations og-awards.jpg ACM Honors & Ethics * Home * Latest Awards News * 2023 Turing Award ACM A.M. Turing Award Honors Avi Wigderson for Foundational Contributions to the Theory of Computation Wigderson is recognized for reshaping our understanding of the role of randomness in computation, and for decades of intellectual leadership in theoretical computer science. ACM has 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. 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 is concerned with the mathematical underpinnings of the field. It poses questions such as "Is this problem solvable through computation?" or "If this problem is solvable through computation, how much time and other resources will be required?" 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? Fundamentally, computers are deterministic systems; the set of instructions of an algorithm applied to any given input uniquely determines its computation and, in particular, its output. In other words, the deterministic algorithm is following a predictable pattern. Randomness , by contrast, lacks a well-defined pattern, or predictability in events or outcomes. Because the world we live in seems full of random events (weather systems, biological and quantum phenomena, etc.), computer scientists have enriched algorithms by allowing them to make random choices in the course of their computation, in the hope of improving their efficiency. And indeed, many problems for which no efficient deterministic algorithm was known have been solved efficiently by probabilistic algorithms, albeit with some small probability of error (that can be efficiently reduced). But is randomness essential, or can it be removed? And what is the quality of randomness needed for the success of probabilistic algorithms? 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 A leader in theoretical computer science research for four decades, Wigderson has made foundational contributions to the understanding of the role of randomness and pseudorandomness in computation. 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 works on 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: * "Hardness vs. Randomness" (co-authored with Noam Nisan) Among other findings, this paper introduced a new type of pseudorandom generator, and proved that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known. * "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (co-authored with Laszlo Babai, Lance Fortnow, and Noam Nisan) This paper used `hardness amplification' to demonstrate that bounded-error probabilistic polynomial time (BPP) can be simulated in subexponential time for infinitely many input lengths under weaker assumptions. * "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (co-authored with Russell Impagliazzo) This paper introduces a stronger pseudo-random generator with essentially optimal hardness vs randomness trade-offs. 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 In addition to his groundbreaking technical contributions, Wigderson is recognized as an esteemed mentor and colleague who has advised countless young researchers. His vast knowledge and unrivaled technical proficiency--coupled with his friendliness, enthusiasm, and generosity--have attracted many of the best young minds to pursue careers in theoretical computer science. "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." News Release | Printable PDF About the ACM A.M. Turing Award The A.M. Turing Award was named for Alan M. Turing, the British mathematician who articulated the mathematical foundation and limits of computing, and who was a key contributor to the Allied cryptanalysis of the Enigma cipher during World War II. Since its inception in 1966, the Turing Award has honored the computer scientists and engineers who created the systems and underlying theoretical foundations that have propelled the information technology industry. 2023 ACM A.M. Turing Award Laureate [wigderson_] Avi 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. 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 Godel 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. Media Coverage * Communications of the ACM: "Wigderson Named Turing Awardee for Decisive Work on Randomness" * Quanta: "Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award" * Nature: "Randomness in computation wins computer-science 'Nobel'" * CTech: "Israeli mathematician Avi Wigderson wins 2023 Turing Prize for insights into randomness" * Haaretz: "Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness" * The Star Ledger / NJ.com: "N.J. professor wins $1M Turing prize for helping teach computers 'randomness'" * New Scientist: "Mathematician wins Turing award for harnessing randomness" * Institute for Advanced Study: "Avi Wigderson Receives 2023 ACM A.M. Turing Award" Notable Papers by Avi Wigderson Avi Wigderson's work has reshaped our understanding of the role of randomness in computation. His important papers on the subject include: * "Hardness vs Randomness" (co-authored with Noam Nisan) introduced a new type of pseudorandom generator, and proved that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known. * "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (co-authored with Laszlo Babai, Lance Fortnow, and Noam Nisan) used "hardness amplification" to demonstrate that bounded-error probabilistic polynomial time (BPP) can be simulated in subexponential time for infinitely many input lengths under weaker assumptions. * "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (co-authored with Russell Impagliazzo) introduced a stronger pseudo-random generator with essentially optimal hardness vs randomness trade-offs. * "In Search of an Easy Witness: Exponential Time vs Probabilistic Polynomial Time" (co-authored with Russell Impagliazzo and Valentine Kabanets) establishes a number of results relating the complexity of exponential-time and probabilistic polynomial-time complexity classes. * "Randomness vs. Time: De-Randomization Under a Uniform Assumption " (co-authored with Russell Impagliazzo) proves that if BPP[?]EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every sampleable ensemble for infinitely many input sizes). * "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" (co-authored with Michael Ben-Or, Shafi Goldwasser, and Joe Kilian) proves that all NP languages have perfect zero-knowledge proof-systems. * "Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems" (co-authored with Oded Goldreich and Silvio Micali ). Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. * About ACM * About ACM * Volunteer * Membership * Join ACM * Renew My Membership * Membership Options * Membership Benefits * MyACM Sign In * Publications * About Publications * Digital Library * Submit a Paper * Chapters * Chapter Admin Interface * Chapter Activities Calendar * Start a Chapter * Awards * About ACM's Awards * Conferences * ACM's Conferences * Code of Ethics * ACM's Code of Ethics * Enforcement Procedures * Media Center * ACM Media Center --------------------------------------------------------------------- ACM Logo * Facebook logo * Twitter logo * LinkedIn logo * Reddit * YouTube logo * Instagram * Flickr * Mastodon * Home * Sitemap * Contact Us * Member Service * Privacy Policy * Accessibility * Cookie Declaration * Copyright (c) 2024, ACM, Inc