2024.0412

Number of words in this article:2494, reading time is about 4 minutes

introduction：他主要研究随机性在计算中的作用，以及协议设计和密码学，奠定了当今大部分数字基础设施的基础。

** Author| ** First Finance and Economics Qian Tongxin

When you toss a coin, which side will face up when it lands? Most people think that "it depends on luck" is "50 - 50".

Is this really the case? Faced with this classic scene, Avi Wigderson, a professor at Princeton University in the United States, pointed out that flipping a coin or rolling a dice is not really random:If you have enough information about physical systems, the results are completely predictable. Perfect randomness is elusive and difficult to verify.

This theory, formed 30 years ago, completely changed the understanding of randomness in computational mathematics and had a profound impact on the progress of computer science.

On April 10, the 2023 winners of the Turing Award, known as the "Nobel Prize in Computing", were announced, and Vigdesen was awarded. The reason is his contributions to the foundations of computational mathematics, including reshaping human understanding of the role of randomness in computing, and decades of leadership in theoretical computer science.

The Turing Award is the highest honor in the field of computer science. In addition to the Turing Award, Wigdesson also shared the 2021 Abel Prize, the highest honor in mathematics, with another scholar. He is also the only person to receive both the Abel Award and the Turing Award.

Mathematics is the foundation of computer science

Yannis Loannidis, president of the American Society for Computer Science (ACM), which awarded the Turing Award, said in a statement released by the organization:"Mathematics is the foundation of computer science, and Wigdesson's work connects a wide range of mathematical subfields with theoretical computer science."

Wigdesson is known for his work on computational complexity theory, where he studies the role of randomness in computing. In a series of influential papers in the 1990s, Wigdesson and colleagues demonstrated that calculations can be equally efficient without randomness, and have shaped algorithm design since then. His research also includes protocol design and cryptography, which lays the foundation for most of today's digital infrastructure.

Xu Chenyang, a professor of mathematics at Princeton University, told the First Financial Reporter:"The field where Wigdesson works is computational complexity, the intersection of mathematics and computers. His influence in the field of pure mathematics has also grown over the years."

Computational complexity theory studies the most common resources, time (how many steps it takes to solve a problem) and space (how much memory is needed to solve a problem), or how many parallel processors are needed to solve a problem in parallel computing.

Wigdesson joined the Princeton Institute for Advanced Study (IAS) in 1999, where he established the computer science and discrete mathematics program. In an interview with the Institute for Advanced Study in Princeton, Wigdesson said that he is both a mathematician and a computer theory scientist, studying the mathematical foundations of computing.

In the 1970s, Wigdesson began his college career at the University of Haifa in Israel. He initially majored in mathematics, but switched to computer science at the advice of his parents. His parents believe that this major is easier to find a job.

Although he had not studied mathematics, Wigdesson quickly discovered that computer science was a field full of unsolved mysteries, and these puzzles were essentially related to mathematics. One of his early pioneering work was to explore a seemingly contradictory question:Can one be convinced that a mathematical proposition has been proved without showing the proof process?

In a series of discoveries at the intersection of mathematics and computer science, Wigdesson's research consolidates the so-called "zero-knowledge proof" theory, which is crucial in cryptography and digital security. Today, Zero-Knowledge Proof (ZKP) technology has been integrated into modern applications such as privacy, compliance, identity verification and blockchain technology.

Princeton University computer scientist Ran Raz commented on Wigdesson:"Avi has many extremely important results in the field of cryptography. The most important theory is zero-knowledge proof."

Wigdesson's influential papers include:Hardness vs. Randomness ("Opposition and Randomness", co-authored with Noam Nisan). This paper introduces a new type of pseudo-random generator and demonstrates that stochastic algorithms can be efficiently and deterministically simulated under weaker assumptions than previously known.

The impact of Wigdesson's theories goes far beyond the fields of randomness and de-randomization, are applied to the broader field of theoretical computer science, and have inspired many leading figures in the field to publish influential papers.

His work is integrated into people's daily lives today

Qiu Chengtong, the first Chinese winner of the Fields Medal, told First Financial Reporter that it was not surprising that Wigdesson won the Turing Award because rather than calling him a mathematician, Wigdesson is a computer scientist. His main research area is computer work. "Of course mathematics is the foundation of all scientific theory." Qiu Chengtong said.

Theoretical computer science focuses on the mathematical foundations of computing, and theoretical computer science is also committed to designing efficient algorithms. In fact, every computing technology that touches our lives is implemented through algorithms. A deep understanding of the principles that make up powerful and efficient algorithms will not only enhance people's understanding of computer science, but also help people better understand the laws of nature.

Randomness is basically a way to ensure that you have a correct understanding of the optimal solution without knowing it. Randomness finds countless other uses in computer science, from cryptography to game theory to machine learning.

It is worth noting that in 2017, Google invested in Princeton IAS and began to study new machine learning methods. Jeff Dean, senior vice president of Google, said that Wigdesson's research has "laid the foundation for the development of theoretical computer science" for decades, and that his work has been directly integrated into people's daily lives.

The First Financial Reporter noticed that in November last year, at the invitation of Yao Qizhi, winner of the 2000 Turing Award and president of the Institute of Cross-Information at Tsinghua University, Vigdersen had just visited the Institute of Cross-Information at Tsinghua University and conducted an "imitation game" academic lecture on the origin and application.

Yao Qizhi said when introducing Vigdesen:"Wigdesson and I have known each other for more than 40 years and are both engaged in computer theory research. Avi has developed unique insights in theory."

Yao Qizhi's research interests include computing theory and its applications in cryptography and quantum computing. He used computers to deal cards and play cards, studied computer theory, and applied this theory to cryptography. To put it bluntly, if business partners send emails to each other, even if they use code words that only both parties understand, there is the possibility of leaks. This involves information security and encryption, and these directions are also highly consistent with Wigdesson's research.

In the report last November, Wigdson started from Alan Turing's "Turing Test" proposed by Alan Turing and described the modern application of "imitation learning" theory in the fields of cryptography, randomness, discrete mathematics, number theory and other fields. Based on cases such as Caesar's Cipher, Enigma machine, and secure elections, he guided students to think about issues such as the definition of security, random applications, and the balance between privacy and utility.

He also responded to what impact the emergence of large-scale large-language models of AI will have on the development direction of theoretical computer research. Regarding how theoretical computer research will respond to the development of artificial intelligence, Wigdesson said:"Although artificial intelligence, including big language models, has many amazing performances, the most important question is what else AI cannot do. I believe that there will always be ceilings in the development of artificial intelligence."

Wigdesson also said that he had spent 40 years solving an open problem and advised students to choose the research field they like and enjoy the process of continuous learning through failure, so that they can go long-term on the road of scientific research.

**