8 ms·

2023 ACM Turing Prize awarded to Avi Wigderson

297 points by nanna 3y ago

srvmshr 3y ago
From ACM: 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. Also of interest, he has won the Abel Prize in 2021, making it a rather unique combination of winning the top honors in both theoretical/abstract math & CS
- polygamous_bat 3y ago
  > Also of interest, he has won the Abel Prize in 2021, making it a rather unique combination of winning the top honors in both theoretical/abstract math & CS The overlap between theoretical CS and math is way larger than most people know. For a simple example, check out the theoretical CS course catalog at MIT: https://catalog.mit.edu/subjects/6/ https://catalog.mit.edu/subjects/6/ and how many of them are cross listed as course 18 (math) classes.
  - vecter 3y ago
    Theoretical CS is basically a branch of applied math
    - waldrews 3y ago
      Perhaps 'an applied branch of math' since the term 'applied math' is claimed by something usually disconnected from the discrete math subjects CS tends to study.
    - Kranar 3y ago
      Theoretical CS is not at all applied math. Ordinary computer science overlaps with applied math, but theoretical CS is very abstract.
  - pfdietz 3y ago
    Highlighting this, Terence Tao gave a tutorial at FOCS 2007. https://terrytao.wordpress.com/2007/07/31/structure-and-randomness-in-combinatorics/ https://terrytao.wordpress.com/2007/07/31/structure-and-rand... Combinatorics seems to be a major subfield on the math side of the border.
- deleted 3y ago
  [deleted]
- jchonphoenix 3y ago
  Technically the Field's medal is the top honor in mathematics. But who am I to talk.
  - Kranar 3y ago
    There's no formal hierarchy so there's nothing technical about it. Field's medal is certainly prestigious but it's not widely applicable, it has a bunch of restrictions that don't have anything to do with math itself, including an age limit. For example no one who has ever been awarded an Abel Prize would qualify for a Field's medal strictly due to age.
    - math_dandy 3y ago
      Six Abel laureates (out of 22) had previously won the Fields Medal: Serre, Aliyah, Thompson, Milner, Deligne, and Margulis.
  - srvmshr 3y ago
    True, it is considered one of the two top honors in Math since last decade. Previously it was the only distinguished prize. There was a growing need for another award which bridged few gaps. The 40 year cutoff age, awarded every 4 years to living mathematical prodigies failed to honor several prominent mathematical breakthroughs which came after decades of painstaking research. As the field has progressed, monumental breakthroughs are harder to come by early into career. Many of the ingenuity comes from cross-study of disciplines for e.g. Riemannian hypothesis being approached by Algebraic geometry and Topology rather than number theory. These require years of mastery - not just prodigy. Also the prize money offered by Abel Foundation is a good incentive for research into pure math
    - sn9 3y ago
      Yes the Fields is much more similar to the MacArthur Genius Grants. The Abel is much more similar to the Nobel, though both the Abel and Fields are Nobel-caliber in prestige.
unethical_ban 3y ago
Congratulations. This was a pretty well written summary by ACM.
COGlory 3y ago
Here's a great Quanta article as well: https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-wigderson-complexity-theo... One thing I enjoyed was the variety of poses they had Wigderson in. It just looks so awkward. "Here, sit in this chair and look out the window longingly".
- jkaptur 3y ago
  > The unreasonable effectiveness of randomness led him to think about the nature of randomness itself. He, like other researchers at the time, questioned how necessary it was for efficient problem-solving and under what conditions it could be eliminated altogether. “Initially, it was not clear if this was only our own stupidity, that we cannot remove randomness,” he said. “But the larger question was whether randomness can always be eliminated efficiently or not.” He realized that the need for randomness was intimately tied to the computational difficulty of the problem. Does anyone have a sketch of how this works? My understanding of complexity classes is that they consider worst case performance. Even if you have a great pseudorandom number generator and a great randomized algorithm, how do you prove that no instance of RNG + seed + problem instance takes exponential time?
  - hinkley 3y ago
    Randomization prevents the worst degenerate cases from being repeatable and thus exploitable. (By an attacker or self-own). Using them is really in the applied CS rather than a theoretical CS domain. The problem can still happen, it just no longer happens consistently to the same customer or at the same time every day. Eliminating the randomized solution was not on my radar so I’ve got some homework to do.
    - pca006132 3y ago
      No, there are complexity classes for random algorithms. And randomness is also crucial for some cryptographic protocols, typically you want to show that the probability the adversary can do what they want is very slim, e.g. 2^-n for some large n.
pthreads 3y ago
Just picked up Wigderson's book and I am liking it so far : https://press.princeton.edu/books/hardcover/9780691189130/mathematics-and-computation https://press.princeton.edu/books/hardcover/9780691189130/ma...
- teleforce 3y ago
  Final draft version of the book available here for personal research and education: https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book
- tinhhuynh_97 3y ago
  Agreed
- myth_drannon 3y ago
  I looked at the book and it's more for graduate-advanced undergrad students. Can someone recommend a more basic book on the topic of computation for someone with a rusty comp-sci/math undergrad background?
  - cryptoxchange 3y ago
    Introduction to the Theory of Computation by Michael Sipser
  - pthreads 3y ago
    Try What Can be Computed by John MacCormick : https://press.princeton.edu/books/hardcover/9780691170664/what-can-be-computed https://press.princeton.edu/books/hardcover/9780691170664/wh...
  - jimhefferon 3y ago
    You could have a look at https://hefferon.net/computation https://hefferon.net/computation which is certainly aimed at a broader audience.
  - sn9 3y ago
    Sipser is the canonical text for undergraduates.
dataexp 3y ago
In (*) Scott Aaronson relates the impact of one of Avi Wigderson talks on his career. https://scottaaronson.blog/?p=2925 https://scottaaronson.blog/?p=2925
wslh 3y ago
More info at "Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness": [1] and its archived version [2] [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.premium/israeli-wins-turing-prize-computings-highest-honor-for-insights-on-randomness/0000018e-c735-dfe9-a19f-f77561e90000 https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p... [2] https://archive.is/e8uix https://archive.is/e8uix
- wslh 3y ago
  [flagged]
WhitneyLand 3y ago
[flagged]
- seanmcdirmid 3y ago
  I really would hate if awards started being handed out to meet diversity requirements. Hopefully we don't get their, and increased diversity in the field today means more diverse Turing awards 30-40 years from now.
  - WhitneyLand 3y ago
    You’re absolutely right they should not! I should’ve clarified that in my comment. I believe awareness and an encouraging and welcoming environment for all are the foundation for everyone to do their best work.
  - wolverine876 3y ago
    That's the standard argument, but it's actually a carefully constructed talking point that (like many such things) twists the premise. The issue is that it's effectively awarded based on a sort of 'diversity requirement' now - white / asian males being the requirement. The evidence is overwhelming - there's no way that's coincidence, or coincidental with all the racial exclusion in the past. Racism, sexism, other forms of prejudice clearly still exist (look at social media if you need a refresher). The question is, what do we do about it?
    - seanmcdirmid 3y ago
      The vast majority of computer scientists up until maybe 10 years ago were white/asian and male. Genius is simply a numbers game, along with a time game to develop it and then be recognized for it. > The question is, what do we do about it? Whatever the answer is, you need to start at the beginning of the pipeline, not the end of it.
      - deleted 3y ago
        [deleted]
hinkley 3y ago
> 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. How would I go about catching up with this aspect of his research? It’s not often that I’ve never heard of a Turing winner, but this guy is completely off of my radar.
- layer8 3y ago
  I wonder what the “standard and widely believed computational assumptions” are. Presumably, probabilistic approximations to NP-complete problems are not polynomial-time? Or the derandomized versions would still be just approximations?
  - reader5000 3y ago
    I think his argument assumes the existence of pseudorandom generators which map a small amount of "true" random bits to a large amount of bits that look random to any polytime observer. The "derandomization" is that we just have to check all possible states of the seed bits which hopefully will be logarithmic in the size of the problem so you can do exhaustive checking.
    - polymipisexp 3y ago
      Nisan and Wigderson prove many different corollaries of their construction in their seminal 'Hardness vs Randomness' paper but their requirement for general derandomization (P = BPP) is that there's some function f computable in time 2^O(n) such that for some e > 0 for all circuits of size 2^en the correlation between f and the output of the circuit is sufficiently low (if I understand correctly).
ode 3y ago
Two of Wigderson's major papers mentioned in the announcement are co-authored with Noam Nisan, one of the professors behind the well known on-line course 'From Nand to Tetris'.
- YouWhy 3y ago
  Prof. Nissan is also remarkable due to having had first line achievements in CS Theory and then shifting to do major impact in the rather distinct field of algorithmic game theory. It's both heart warming that a single person living today could be as diverse, and that the system allowed him that flexibility.
- sn9 3y ago
  There's a book, too! Recently came out as a second edition.
thedatamonger 3y ago
From the related article: https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-wigderson-complexity-theo... > ... if a statement can be proved, it also has a zero-knowledge proof. Mind blown. >Feeding the pseudorandom bits (instead of the random ones) into a probabilistic algorithm will result in an efficient deterministic one for the same problem. This is nuts. AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude. If I'm living in noobspace someone please pull me out.
- IshKebab 3y ago
  I don't know exactly what it's saying but it definitely isn't that. AI already uses pseudorandom numbers and is deterministic. (Except some weird AI accelerator chips that use analogue computation to improve efficiency.)
- ilya_m 3y ago
  > AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude. Unfortunately, no. First, the result applies to decision, not search problems. Second, the resulting deterministic algorithm is much less efficient than the randomized algorithm, albeit it still belongs to the same complexity class (under some mild assumptions).
  - mxkopy 3y ago
    Can’t you build search from decision by deciding on every possible input?
rramadass 3y ago
Any study recommendations (beginner friendly to advanced) on this topic i.e. Probability/Randomness and Computation? Google brings up Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Eli Upfal and Michael Mitzenmacher but i can't find any beginner/introductory books/articles/videos.
tu7001 3y ago
Anyone some good Avi youtube videos?
tialaramex 3y ago
That headline phrasing reads weird to me, obviously people from various allied disciplines might be expected to win the Turing Award, so it's not completely redundant but it's not so far from "Movie wins Best Picture Oscar" and "Sprinter wins Olympic 100m medal".
Daub 3y ago
I love this section of the article (edited for clarity): "I'm not motivated by application, but I know that we can find uses for fundamental work. Think about Alan Turing. He wrote a mathematical paper in logic in an obscure journal about Entscheidungsproblem. It was not motivated by application." This is similar to Feynman's plate story, which started off as a casual response to an observation he made in a university canteen, and which ended in a Nobel prize. To extend my point, it is precisely this kind of curiosity-based enquiry that modern academia discourages.

297 points by nanna 3y ago

From ACM: 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. Also of interest, he has won the Abel Prize in 2021, making it a rather unique combination of winning the top honors in both theoretical/abstract math & CS

polygamous_bat 3y ago
> Also of interest, he has won the Abel Prize in 2021, making it a rather unique combination of winning the top honors in both theoretical/abstract math & CS The overlap between theoretical CS and math is way larger than most people know. For a simple example, check out the theoretical CS course catalog at MIT: https://catalog.mit.edu/subjects/6/ https://catalog.mit.edu/subjects/6/ and how many of them are cross listed as course 18 (math) classes.
- vecter 3y ago
  Theoretical CS is basically a branch of applied math
  - waldrews 3y ago
    Perhaps 'an applied branch of math' since the term 'applied math' is claimed by something usually disconnected from the discrete math subjects CS tends to study.
  - Kranar 3y ago
    Theoretical CS is not at all applied math. Ordinary computer science overlaps with applied math, but theoretical CS is very abstract.
- pfdietz 3y ago
  Highlighting this, Terence Tao gave a tutorial at FOCS 2007. https://terrytao.wordpress.com/2007/07/31/structure-and-randomness-in-combinatorics/ https://terrytao.wordpress.com/2007/07/31/structure-and-rand... Combinatorics seems to be a major subfield on the math side of the border.
deleted 3y ago
[deleted]
jchonphoenix 3y ago
Technically the Field's medal is the top honor in mathematics. But who am I to talk.
- Kranar 3y ago
  There's no formal hierarchy so there's nothing technical about it. Field's medal is certainly prestigious but it's not widely applicable, it has a bunch of restrictions that don't have anything to do with math itself, including an age limit. For example no one who has ever been awarded an Abel Prize would qualify for a Field's medal strictly due to age.
  - math_dandy 3y ago
    Six Abel laureates (out of 22) had previously won the Fields Medal: Serre, Aliyah, Thompson, Milner, Deligne, and Margulis.
- srvmshr 3y ago
  True, it is considered one of the two top honors in Math since last decade. Previously it was the only distinguished prize. There was a growing need for another award which bridged few gaps. The 40 year cutoff age, awarded every 4 years to living mathematical prodigies failed to honor several prominent mathematical breakthroughs which came after decades of painstaking research. As the field has progressed, monumental breakthroughs are harder to come by early into career. Many of the ingenuity comes from cross-study of disciplines for e.g. Riemannian hypothesis being approached by Algebraic geometry and Topology rather than number theory. These require years of mastery - not just prodigy. Also the prize money offered by Abel Foundation is a good incentive for research into pure math
  - sn9 3y ago
    Yes the Fields is much more similar to the MacArthur Genius Grants. The Abel is much more similar to the Nobel, though both the Abel and Fields are Nobel-caliber in prestige.

unethical_ban 3y ago

Congratulations. This was a pretty well written summary by ACM.

COGlory 3y ago

Here's a great Quanta article as well: https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-wigderson-complexity-theo... One thing I enjoyed was the variety of poses they had Wigderson in. It just looks so awkward. "Here, sit in this chair and look out the window longingly".

jkaptur 3y ago
> The unreasonable effectiveness of randomness led him to think about the nature of randomness itself. He, like other researchers at the time, questioned how necessary it was for efficient problem-solving and under what conditions it could be eliminated altogether. “Initially, it was not clear if this was only our own stupidity, that we cannot remove randomness,” he said. “But the larger question was whether randomness can always be eliminated efficiently or not.” He realized that the need for randomness was intimately tied to the computational difficulty of the problem. Does anyone have a sketch of how this works? My understanding of complexity classes is that they consider worst case performance. Even if you have a great pseudorandom number generator and a great randomized algorithm, how do you prove that no instance of RNG + seed + problem instance takes exponential time?
- hinkley 3y ago
  Randomization prevents the worst degenerate cases from being repeatable and thus exploitable. (By an attacker or self-own). Using them is really in the applied CS rather than a theoretical CS domain. The problem can still happen, it just no longer happens consistently to the same customer or at the same time every day. Eliminating the randomized solution was not on my radar so I’ve got some homework to do.
  - pca006132 3y ago
    No, there are complexity classes for random algorithms. And randomness is also crucial for some cryptographic protocols, typically you want to show that the probability the adversary can do what they want is very slim, e.g. 2^-n for some large n.

pthreads 3y ago

Just picked up Wigderson's book and I am liking it so far : https://press.princeton.edu/books/hardcover/9780691189130/mathematics-and-computation https://press.princeton.edu/books/hardcover/9780691189130/ma...

teleforce 3y ago
Final draft version of the book available here for personal research and education: https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book
tinhhuynh_97 3y ago
Agreed
myth_drannon 3y ago
I looked at the book and it's more for graduate-advanced undergrad students. Can someone recommend a more basic book on the topic of computation for someone with a rusty comp-sci/math undergrad background?
- cryptoxchange 3y ago
  Introduction to the Theory of Computation by Michael Sipser
- pthreads 3y ago
  Try What Can be Computed by John MacCormick : https://press.princeton.edu/books/hardcover/9780691170664/what-can-be-computed https://press.princeton.edu/books/hardcover/9780691170664/wh...
- jimhefferon 3y ago
  You could have a look at https://hefferon.net/computation https://hefferon.net/computation which is certainly aimed at a broader audience.
- sn9 3y ago
  Sipser is the canonical text for undergraduates.

dataexp 3y ago

In (*) Scott Aaronson relates the impact of one of Avi Wigderson talks on his career. https://scottaaronson.blog/?p=2925 https://scottaaronson.blog/?p=2925

wslh 3y ago

More info at "Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness": [1] and its archived version [2] [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.premium/israeli-wins-turing-prize-computings-highest-honor-for-insights-on-randomness/0000018e-c735-dfe9-a19f-f77561e90000 https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p... [2] https://archive.is/e8uix https://archive.is/e8uix

wslh 3y ago
[flagged]

WhitneyLand 3y ago

[flagged]

seanmcdirmid 3y ago
I really would hate if awards started being handed out to meet diversity requirements. Hopefully we don't get their, and increased diversity in the field today means more diverse Turing awards 30-40 years from now.
- WhitneyLand 3y ago
  You’re absolutely right they should not! I should’ve clarified that in my comment. I believe awareness and an encouraging and welcoming environment for all are the foundation for everyone to do their best work.
- wolverine876 3y ago
  That's the standard argument, but it's actually a carefully constructed talking point that (like many such things) twists the premise. The issue is that it's effectively awarded based on a sort of 'diversity requirement' now - white / asian males being the requirement. The evidence is overwhelming - there's no way that's coincidence, or coincidental with all the racial exclusion in the past. Racism, sexism, other forms of prejudice clearly still exist (look at social media if you need a refresher). The question is, what do we do about it?
  - seanmcdirmid 3y ago
    The vast majority of computer scientists up until maybe 10 years ago were white/asian and male. Genius is simply a numbers game, along with a time game to develop it and then be recognized for it. > The question is, what do we do about it? Whatever the answer is, you need to start at the beginning of the pipeline, not the end of it.
    - deleted 3y ago
      [deleted]

hinkley 3y ago

> 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. How would I go about catching up with this aspect of his research? It’s not often that I’ve never heard of a Turing winner, but this guy is completely off of my radar.

layer8 3y ago
I wonder what the “standard and widely believed computational assumptions” are. Presumably, probabilistic approximations to NP-complete problems are not polynomial-time? Or the derandomized versions would still be just approximations?
- reader5000 3y ago
  I think his argument assumes the existence of pseudorandom generators which map a small amount of "true" random bits to a large amount of bits that look random to any polytime observer. The "derandomization" is that we just have to check all possible states of the seed bits which hopefully will be logarithmic in the size of the problem so you can do exhaustive checking.
  - polymipisexp 3y ago
    Nisan and Wigderson prove many different corollaries of their construction in their seminal 'Hardness vs Randomness' paper but their requirement for general derandomization (P = BPP) is that there's some function f computable in time 2^O(n) such that for some e > 0 for all circuits of size 2^en the correlation between f and the output of the circuit is sufficiently low (if I understand correctly).

ode 3y ago

Two of Wigderson's major papers mentioned in the announcement are co-authored with Noam Nisan, one of the professors behind the well known on-line course 'From Nand to Tetris'.

YouWhy 3y ago
Prof. Nissan is also remarkable due to having had first line achievements in CS Theory and then shifting to do major impact in the rather distinct field of algorithmic game theory. It's both heart warming that a single person living today could be as diverse, and that the system allowed him that flexibility.
sn9 3y ago
There's a book, too! Recently came out as a second edition.

thedatamonger 3y ago

From the related article: https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-wigderson-complexity-theo... > ... if a statement can be proved, it also has a zero-knowledge proof. Mind blown. >Feeding the pseudorandom bits (instead of the random ones) into a probabilistic algorithm will result in an efficient deterministic one for the same problem. This is nuts. AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude. If I'm living in noobspace someone please pull me out.

IshKebab 3y ago
I don't know exactly what it's saying but it definitely isn't that. AI already uses pseudorandom numbers and is deterministic. (Except some weird AI accelerator chips that use analogue computation to improve efficiency.)
ilya_m 3y ago
> AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude. Unfortunately, no. First, the result applies to decision, not search problems. Second, the resulting deterministic algorithm is much less efficient than the randomized algorithm, albeit it still belongs to the same complexity class (under some mild assumptions).
- mxkopy 3y ago
  Can’t you build search from decision by deciding on every possible input?

rramadass 3y ago

Any study recommendations (beginner friendly to advanced) on this topic i.e. Probability/Randomness and Computation? Google brings up Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Eli Upfal and Michael Mitzenmacher but i can't find any beginner/introductory books/articles/videos.

tu7001 3y ago

Anyone some good Avi youtube videos?

tialaramex 3y ago

That headline phrasing reads weird to me, obviously people from various allied disciplines might be expected to win the Turing Award, so it's not completely redundant but it's not so far from "Movie wins Best Picture Oscar" and "Sprinter wins Olympic 100m medal".

Daub 3y ago

I love this section of the article (edited for clarity): "I'm not motivated by application, but I know that we can find uses for fundamental work. Think about Alan Turing. He wrote a mathematical paper in logic in an obscure journal about Entscheidungsproblem. It was not motivated by application." This is similar to Feynman's plate story, which started off as a casual response to an observation he made in a university canteen, and which ended in a Nobel prize. To extend my point, it is precisely this kind of curiosity-based enquiry that modern academia discourages.