The white color is from the Au Fei Temple
量子位 | 公众号 QbitAI
Just now, the Turing Award, the "highest honor in the computer industry", was announced——
Avi Wigderson, a pioneer in complexity theory and a professor at the Institute for Advanced Study in Princeton, won the prize.
The Association for Computing Machinery (ACM) recognized him for his foundational contributions to the theory of computing, including reshaping humanity's understanding of the role of randomness in computing, as well as decades of leadership in theoretical computer science.
Together with the Abel Prize in 2021, Professor Wigson is now the first scientist to win the top prize in mathematics and computing at the same time.
(The Abel Prize is also known as the "Nobel Prize in Mathematics").
In addition, he was also one of the first "Top Ten Patriarchs" when the Ali Dharma Academy was first established in 2017.
Industry insiders rushed to congratulate him, and the R&D director of a16z said that in addition to the existing academic achievements, it is also because of his tireless leadership for decades that has brought the evergreen and vitality of the theoretical computer science community.
For example, without him, there might not be the Simmons Institute for Computational Theory.
It is worth mentioning that he also came to Tsinghua Fork Institute as a guest 5 months ago and expressed his views on the current development of large language models.
Complexity Theory Pioneer Wins Turing Award
As a mathematician and computer scientist, Wigson's most important contribution was to enhance the understanding of the role of randomness and pseudo-randomness in computing.
What does that mean exactly?
In the late 20's and 70's, computer scientists have discovered:
There is a significant correlation between randomness and computational difficulty.
(Computationally difficult here refers to natural problems that do not have effective algorithms, i.e., cannot be solved in a reasonable amount of time, and are computationally difficult.) ）
In layman's terms, it is:
For many puzzles, algorithms that employ randomness, also known as probabilistic algorithms, can far outweigh their deterministic solutions.
For example, in an implementation known as the "1977 proof," two scientists introduced a stochastic algorithm that could determine whether a number was prime faster than the best deterministic algorithms of the time.
And in the early 80s of the 20th century, Wigson collaborated with Richard Karp, a scientist at UC Berkeley, to link the concept of randomness to problems that are considered computationally difficult, that is, problems for which there is no known deterministic algorithm that can solve them in a reasonable amount of time.
Despite not knowing how difficult it was to prove them, Wigson and Richard Karp discovered a stochastic algorithm for a difficult problem and then discovered that being able to derandomize it effectively revealed its deterministic algorithm.
Around the same time, other researchers also found that the computational difficulty assumption in cryptography problems enabled general derandomization.
This prompted Wigson to think about the nature of randomness itself.
He, like everyone else, began to question the necessity of randomness in efficient problem solving and under what conditions it could be eliminated altogether.
Finally, in 1994, he and another computer scientist, Noam Nisan, shed light on the connection between the two.
They proved that if there were any natural puzzles, then every valid stochastic algorithm could be replaced by a valid deterministic algorithm.
i.e. we can always eliminate randomness.
What's more, they also found that deterministic algorithms may use "pseudo-random" sequences – strings of data that appear to be random but are not.
In other words, randomness is not necessary for efficient computation.
Even in the absence of randomness, we can still use an effective algorithm to solve the problem.
This series of research has revolutionized the way computer scientists think about randomness and is applicable to many areas of theoretical computer science.
Today, ACM is awarding the Turing Award to Wigson, mainly for his contributions to the above fields.
In an interview with the Institute for Advanced Study in Princeton, Wigson explained that he was both a mathematician and a computer theory scientist who studied the mathematical foundations of computing.
My field of study is a subdomain of mathematics, but at the same time, the main concept I study is computing.
In the case of theoretical computer science, he argues that the discipline has all the virtues one can expect from an academic research, encompassing a surprisingly profound and intellectually significant set of fundamental questions that are essential to humanity, science, life, and technology.
(You can see the old man's full of love.) ）
For this award, Wigson said:
I am glad to see that ACM has once again recognized the fundamental theory of computing, which has indeed made a great contribution to the practice and technical development of computing science.
University was advised to study computer science "easy to find a job"
Wigson was born in Israel in 1956, the son of a nurse and an electrical engineer. His father loved puzzles and was very interested in the basic concepts of mathematics, and then often shared his ideas with the children.
Wigson described his father's subtle influence on him this way: He was the one who infected me with the virus.
However, when he was about to study at the local University of Haifa, he wanted to major in mathematics, but his parents persuaded him:
Choose a computer, it's easy to find a job!
As a result, he found that there were many unsolved mathematical problems in this field, so he began to solve them in a hurry.
A graduate of the Technion-Israel Institute of Technology and Princeton University, Wigson received his Ph.D. in 1983 with his dissertation, A Study of Combinatorial Complexity.
One of his early seminal works was to demonstrate a seemingly paradoxical problem:
Is it possible to convince others that a mathematical thesis has been proven without showing the proof process?
Do you think of the millionaire problem raised by Yao Qizhi in the field of privacy computing?
That question is two millionaires who want to prove who is richer, but neither of them reveals how much wealth they have.
The original problem was actually called zero-knowledge proof, and the concept was first introduced by three scientists in 1985. This idea was then further elaborated by Wigson and his partners Micali and Oded Goldreich, who found an unexpected result: if truly secure encryption were possible, the solution to every problem in the NP could also be proven with zero-knowledge proofs.
In other words, zero-knowledge proofs can be used to secretly prove the public results of any secret data.
He has been active in academic positions for decades and has received numerous accolades and awards. In 1994, he was awarded the 1994 Nevan Linner for his work on computational complexity theory
After completing his Ph.D., he worked as a visiting assistant professor at the University of California, Berkeley, a visiting scientist at IBM, and a researcher at the Institute of Mathematical Sciences in Berkeley. He joined the Hebrew University as a faculty member in 1986.
In 1994, he received the 2009 Gödel Prize for his work on the zig-zag product of graphs, along with Omer Reingold and Salil Vadhan.
In 1999, he joined the Institute for Advanced Study in Princeton, where he has been since then. In 2013, he was elected to the National Academy of Sciences.
In 2018, he was elected an ACM Fellow for his contributions to computer science and mathematical theory.
The following year, he was awarded the Gartner Prize for "fundamental and enduring contributions to the foundations of computer science in the fields of random computing, cryptography, circuit complexity, proof complexity, parallel computing, and our understanding of the properties of fundamental graphs."
2021年,维格森与Laszlo Lovász共同获得阿贝尔奖。
It is precisely because of such a fundamental and lasting contribution that netizens were surprised and pleasantly surprised when they learned that he had won the Turing Award, and thought that he had already won it.
Some people are starting to read the books he used to write.
Maybe you have a familiar friend?
Talking about large language models: the most important thing is to see what it can't do
And his fate with Yao Qizhi and China continues.
Five months ago, he also came to Tsinghua Fork Academy as a guest to bring a special report entitled "Imitation Games".
Academician Yao Chi-chi personally presided over the lecture and started a dialogue with him.
Starting from the Turing test, Wigson reportedly described the evolution of the theory of "imitation learning" and its modern applications in the fields of cryptography, randomness, discrete mathematics, and number theory.
Based on cases such as Caesar's cipher, Enigma cipher, and election, he led him to think about the definition of security, the application of randomness, and the balance between privacy and utility.
As for how theoretical computer research will respond to the development of artificial intelligence, Wigson said,
Although there are many amazing performances of AI, including large language models, the most important question is what else AI can't do.
For students who are now engaged in scientific research, Wigson also gave his own advice.
He said that he had spent 40 years solving an open problem, and suggested that students should choose their favorite research fields and topics, and enjoy the process of continuous learning from failure, so that they can go long on the road of scientific research.
Reference Links:
[1]https://www.acm.org/media-center/2024/april/turing-award-2023
[2]https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award
[3]https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/
[4]https://www.youtube.com/watch?v=TK_vD-VnsFw
[5]https://x.com/Tim_Roughgarden/status/1778032735849967818
[6]https://x.com/letonyo/status/1777987622301769771
— END —
QbitAI · Headline number signed
Follow us and be the first to know about cutting-edge technology trends