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
> 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/ and how many of them are cross listed as course 18 (math) classes.
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.
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.
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
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".
> 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?
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.
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.
In crypto we are worried about the best case scenario (from the attacker’s perspective).
Randomization in algorithms, to avoid worst case behavior, would be things like shuffling input, XORing hashes for query parameters per run or per hash table, or using random tiebreakers.
Yeah randomization in algorithms and crypto serve different purpose. But overall introducing randomness can allow you to do amazing things that deterministic algorithm/schemes cannot do.
> In crypto we are worried about the best case scenario (from the attacker’s perspective).
That seems mistaken to me. The best case in most crypto, from an attacker's perspective, is "I tried one key and just happened to get it right". Aren't we more interested in expected outcomes?
In the sense of big O you’re right and I misspoke.
When we are deciding to retire an algorithm it’s often down to how many unaddressed weaknesses there are and assuming that they compose. That’s the best case I was referring to.
For example there's an easy randomized algorithm to determine a quadratic nonresidue modulo a prime with success probability 1/2 per Legendre symbol evaluation. In expectation this is 2 iterations, and that's independent of the prime. The best known deterministic algorithm takes log(p)^2 such evaluations in the worst case, even assuming generalized Riemann hypothesis.
BPP is the complexity class for decision problems that a randomized algorithm can solve in polynomial time, in the sense that on every input (worst-case), the algorithm is right with at least 2/3 probability (over its own randomness).
One example is deciding whether a given number is prime. For a long time, we knew randomized algorithms like the Miller-Rabin test that are correct with high probability. That is, we knew PRIMES is in BPP. But we didn't know a deterministic algorithm. In 2006, a deterministic algorithm was discovered, proving that PRIMES is in P.
One of the central open problems in Computer Science is whether BPP=P. That is, for any problem we can solve with randomness (in the above sense), can we solve it without randomness? Among many other contributions, Wigderson's work has made a ton of progress toward this problem.
The general idea is to try to "derandomize" any randomized algorithm that runs in polynomial time and is correct with 2/3 probability. We will feed it inputs from a pseudorandom generator (instead of true random numbers). If the PRG is really really good, then we can get a deterministic algorithm by running the original algorithm along with the PRG.
Now, if we can prove certain problems are hard, then we can also prove that such really really good PRGs exist. This is basically because telling apart the PRG from true randomness would be a computationally hard problem.
> BPP is the complexity class for decision problems that a randomized algorithm can solve in polynomial time, in the sense that on every input (worst-case), the algorithm is right with at least 2/3 probability (over its own randomness).
What's the theoretical significance of the 2/3 threshold?
None, it can actually be any constant > 1/2, because you can always run the algorithm a non-exponential number of more times to be more convinced (approaching prob 1) of the answer. 2/3 is just convention.
Dumb question: There exist randomized approximation algorithms for Weighted Hitting Set, yet it is NP-Hard. Assuming I haven't said anything dumb yet, this surely should satisfy it: Why does this not prove BPP != P?
Perhaps: Am I incorrect in assuming that randomized 2-approximation is somehow transformable to 'correctness in the decision problem 2/3 of the time'?
I realize that, but can you help me see why that's relevant here? The question as I understood it was BPP?=P, and I read that as "Do all problems that seem hard but have randomized algorithms actually live in P?" for which a counter example would be an NP-Hard problem with good randomized solution, right?
(Not who you asked, but) one important point here is definitely that BPP is about yes/no decision problems, and approximation algorithms are generally a different beast.
> Perhaps: Am I incorrect in assuming that randomized 2-approximation is somehow transformable to 'correctness in the decision problem 2/3 of the time'?
Yes, that's the issue. For another example, Max-Cut is NP-hard. We can easily get a randomized 2-approximation by taking a cut in the graph uniformly at random (don't even look at the graph structure). But it doesn't look possible to go from this totally random 2-approximation to a correct guess about the size of the true max cut.
An important idea is to use what are called worst-case-to-average-case reductions. You convert a boolean function f that is worst-case hard to another function g which is average-case hard. In other words, if g is average-case easy, then f is worst-case easy.
These reductions are a major achievement in complexity theory. Constructions use tools like combinatorial designs, list-decoding of error-correcting codes, expander graphs, extractors etc. A good overview of these methods is in Arora and Barak's "Computational complexity", in, I believe Chapters 19 through 21.
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.
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.
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 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.
I think it's a fantasy that there is not significant prejudice at the end of the pipeline, where we are. Everyone seems to have that fantasy about themeselves, their organization, their community, etc.
The answer starts, as with every problem, by looking carefully in the mirror, with fresh eyes, as if there was a stranger staring back. Then look at your own organization, your own community, etc.
I know there is discrimination at the end of the pipeline, there has been for a few years now, but it isn't in the direction that you think its in, and it isn't relevant to who is winning a once a year award that is based on work someone started 40+ years ago.
It is exactly in that direction; just look at the outcomes. You take the long-term standard, where white (and Asian) males get advantages, and normalize it - norms are unremarkable, the null hypothesis. Changing the norm then looks like discrimination.
Because deciding model trust is a function of how the stakes are for doing so combined with how many other indicators you have suggesting the data is reliable.
In this case it seemed to have worked, no one is really disputing the accuracy and instead seem to feel quite strongly about what it suggests.
> 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.
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?
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.
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).
They are generally esoteric conjectures similar in spirit to P != NP. For example, the third paper uses the assumption "E requires exponential circuits". Here E is the class of problems solvable in exponential time, or 2^O(n) time, on a Turing Machine. Another model of computation besides Turing Machines are Boolean circuits, i.e. AND, OR, and NOT gates. The conjecture is that not every problem in E can be solved by "small" (subexponential-sized) circuits.
The basic idea of the work is that if these problems are hard, then we can use them to build pseudorandom generators that are "just as good" as true random, which we can use to turn truly random algorithms into pseudorandom algorithms with the same performance.
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'.
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.
> ... 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.
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.)
> 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).
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.
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".
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.
80 comments
[ 3.4 ms ] story [ 40.2 ms ] threadACM 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
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/ and how many of them are cross listed as course 18 (math) classes.
https://terrytao.wordpress.com/2007/07/31/structure-and-rand...
Combinatorics seems to be a major subfield on the math side of the border.
But who am I to talk.
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
The Abel is much more similar to the Nobel, though both the Abel and Fields are Nobel-caliber in prestige.
This was a pretty well written summary by ACM.
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".
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?
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.
Randomization in algorithms, to avoid worst case behavior, would be things like shuffling input, XORing hashes for query parameters per run or per hash table, or using random tiebreakers.
That seems mistaken to me. The best case in most crypto, from an attacker's perspective, is "I tried one key and just happened to get it right". Aren't we more interested in expected outcomes?
When we are deciding to retire an algorithm it’s often down to how many unaddressed weaknesses there are and assuming that they compose. That’s the best case I was referring to.
For example there's an easy randomized algorithm to determine a quadratic nonresidue modulo a prime with success probability 1/2 per Legendre symbol evaluation. In expectation this is 2 iterations, and that's independent of the prime. The best known deterministic algorithm takes log(p)^2 such evaluations in the worst case, even assuming generalized Riemann hypothesis.
One example is deciding whether a given number is prime. For a long time, we knew randomized algorithms like the Miller-Rabin test that are correct with high probability. That is, we knew PRIMES is in BPP. But we didn't know a deterministic algorithm. In 2006, a deterministic algorithm was discovered, proving that PRIMES is in P.
One of the central open problems in Computer Science is whether BPP=P. That is, for any problem we can solve with randomness (in the above sense), can we solve it without randomness? Among many other contributions, Wigderson's work has made a ton of progress toward this problem.
The general idea is to try to "derandomize" any randomized algorithm that runs in polynomial time and is correct with 2/3 probability. We will feed it inputs from a pseudorandom generator (instead of true random numbers). If the PRG is really really good, then we can get a deterministic algorithm by running the original algorithm along with the PRG.
Now, if we can prove certain problems are hard, then we can also prove that such really really good PRGs exist. This is basically because telling apart the PRG from true randomness would be a computationally hard problem.
What's the theoretical significance of the 2/3 threshold?
Perhaps: Am I incorrect in assuming that randomized 2-approximation is somehow transformable to 'correctness in the decision problem 2/3 of the time'?
Yes, that's the issue. For another example, Max-Cut is NP-hard. We can easily get a randomized 2-approximation by taking a cut in the graph uniformly at random (don't even look at the graph structure). But it doesn't look possible to go from this totally random 2-approximation to a correct guess about the size of the true max cut.
These reductions are a major achievement in complexity theory. Constructions use tools like combinatorial designs, list-decoding of error-correcting codes, expander graphs, extractors etc. A good overview of these methods is in Arora and Barak's "Computational complexity", in, I believe Chapters 19 through 21.
> The original version of this article said Wigderson attended the University of Haifa. He actually graduated from the Technion, in Haifa, Israel.
How did the reporter mess that up?
I can see the reporter reading that he attended university in Haifa and misconstruing that to mean the University of Haifa...
https://press.princeton.edu/books/hardcover/9780691189130/ma...
https://www.math.ias.edu/avi/book
Can someone recommend a more basic book on the topic of computation for someone with a rusty comp-sci/math undergrad background?
https://press.princeton.edu/books/hardcover/9780691170664/wh...
https://scottaaronson.blog/?p=2925
[1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
[2] https://archive.is/e8uix
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.
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?
> 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.
The answer starts, as with every problem, by looking carefully in the mirror, with fresh eyes, as if there was a stranger staring back. Then look at your own organization, your own community, etc.
It is exactly in that direction; just look at the outcomes. You take the long-term standard, where white (and Asian) males get advantages, and normalize it - norms are unremarkable, the null hypothesis. Changing the norm then looks like discrimination.
In this case it seemed to have worked, no one is really disputing the accuracy and instead seem to feel quite strongly about what it suggests.
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.
The basic idea of the work is that if these problems are hard, then we can use them to build pseudorandom generators that are "just as good" as true random, which we can use to turn truly random algorithms into pseudorandom algorithms with the same performance.
Recently came out as a second edition.
> ... 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.
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).
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.
"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.