For the first time in China!Tsinghua Yao Ban undergraduates won the Global Award of Global Theoretical Computer

Author:Scientific network Time:2022.06.22

Text | "China Science News" reporter Zhang Qingdan

A team consisting of three undergraduates in China has recently calculated the theoretical annual conference (STOC) to defeat many masterpieces and won the best student thesis award.

This result is not easy. First, STOC was organized by the American Computer Association (ACM) and on the peak of theoretical computer science, it was a well -deserved peak meeting; second, their papers highlighted from more than 400 papers around the world, making it domestic The only team that has won this award; Third, this is the first time that Chinese college students have won the award.

All three students are from the "Yao Ban" of Tsinghua University, namely Fan Zhiyuan, Li Jiatu and Yang Tianqi. They are about to participate in the STOC 2022 on June 23, "We are hurrying up to prepare for STOC's speech video!"

The figures are Fan Zhiyuan, Li Jiatu and Yang Tianqi. Interviewee confidence

The three post -00s school fighters far ahead of their peers have not been too much. "Theoretical computer science research is like a vast sea. What we have done is the tip of the iceberg, it is the foundation. In the future To solve the important issues of computing complexity. "

Youzhong selection: the award rate is only about 2.9%

There are two major meetings in the field of theoretical computer science, one is the STOC of ACM (American Computer Society), and the other is FOCS of IEEE (International Electrical and Electronic Engineers Association). Both have lofty reputation and are the most difficult conference representatives.

A total of 457 papers voted in STOC worldwide this year, receiving 135 articles, and a receiving rate of about 29%.

Among them, 2 best thesis awards, and 2 best student thesis awards, the award rate is only about 2.9%. The best student thesis requires all participants to be a student below a doctorate degree. The competition is very fiercely competitive worldwide. It is difficult for undergraduates to be "on the list" even under undergraduate students such as Massachusetts Institute of Technology and Princeton University.

Two papers that have won the best thesis awards are from the Institute of Science of Weitzman, Hebrew University, and Moscow National University. Picture source: stoc official website

Two papers of the Best Student Paper Awards are from Microsoft Research Institute, MIT Institute of Technology, and Tsinghua University. Picture source: stoc official website

On the highest stage gathered by the masters, Fan Zhiyuan, Li Jiatu and Yang Tianqi jointly completed the papers "The precise complexity of the pseudo -random function and the black box naturally proved the obstacles of the black box naturally proved" in the theory of computational complexity, which is not easy.

The study of this paper is pioneering. The thesis studied the circuit complexity of the pseudo -random function, and the pseudo -random function was given to the pseudo -random function in multiple important circuit complexity classes. These upper and lower bounds have provided new understanding for the theory of circuit complexity, and also explained why some of the widespread conjectures are difficult to prove.

According to the "China Science News", these three students were not in a team from the beginning. The original prototype was proposed by Li Jiatu and Yang Tianqi.

In the semester, the computer applied mathematics course taught by Yao Qizhi, a world -renowned computer scientist and academician of the Chinese Academy of Sciences, benefited Li Jiatu and Yang Tianqi. "We realize that computer science is a discipline that can generate many interesting, inspiration and experience to solve."

In order to learn more about computer science, they took the computing theoretical courses of Teacher Duan Ran in advance in the semester. It is this course that they have learned that there are many unspeakable problems in the field of computing complexity, and there are many directions that have just started and need to be further explored.

The two consulted various related documents after class. In addition to trying to make up for the lack of knowledge, they also wanted to find the goal direction. During that time, they watched an important breakthrough in the theory of circuit complexity in recent years, which was proposed by Ryan Williams, a professor at Massachusetts Institute of Technology that proves that the algorithm method of Circuit Lower Bound (Algorithmic Approach).

"We want to start with the cutting -edge issues of a circuit complexity theory to understand the background, main technologies, and current important issues of this field." Li Jiatu said in an interview with the China Science News.

However, the actual progress is not satisfactory. After some learning, although the two generally understood the basic theory of this method, they did not find the question that could be further explored.

After the spring semester of 2021, after they took the basic curriculum taught by Mr. Chen Yimui, they suddenly felt "Liu Dahua Ming".

"We thought in our studies whether the cryptography can be linked to the complication of the circuit complication we studied before, and the amount of computing resources required for the computing system to be compiled through the technology of the circuit complexity to complete the computing resources required by the curriculum. "Li Jiatu said.

All the students who elect the course must be based on a group to make a Final Project report in the class. It happened that Fan Zhiyuan also took the course. After listening to the report of Li Jiatu and Yang Tianqi, he took the initiative to find the two, and proposed that this result can have a lot of room for improvement.

"Before Fan Zhiyuan joined, we only got a border of complexity for one circuit model at that time. The results were weak and the technology was relatively complicated. It mainly pointed out a vague direction for subsequent studies." Yang Tianqi told the China Science News. The appearance of Fan Zhiyuan was like rain in time. Not only did he put forward improvements, but also greatly increased Li Jiatu and Yang Tianqi's confidence in solving this problem.

After the combination of "2+1", the advantage is complementary and the strength has increased greatly.

"The atmosphere of the three of us is very comfortable. Everyone often exchanges and discuss, and the thoughts will collide with a lot of sparks. Later, we have greatly simplified and improved the original method, and we explore this issue with completely different technologies. More side. "Fan Zhiyuan told the China Science News.

Related studies have a qualitative leap, so that in the final paper, the original preset issues are no longer the most important result, and the result of the final display is particularly outstanding -proved the upper and lower bounds in the three models.

Yao Ban: "Great God" gathering place

Among the 135 papers received in this STOC, there were 7 teachers and students from Yao Ban. In the papers received by previous STOCs, the teachers and students of Yao Ban also appeared. For example, there were 4 articles in 2020 and 3 articles in 2021.

The last Chinese who won the STOC Best Student Paper was Chen Lijie, and he also graduated from Yao Ban. Now he is studied at the Massachusetts Institute of Technology, and Ryan Williams mentioned in the above is his mentor.

In the hearts of many Yao class students, Chen Lijie is the role model for them to learn, and it is the same existence of "BUG": he won the gold medal of the 2011 Asia -Pacific Information Olympic Contest, which is the first place in the 2013 International Information Science Olympic Competition, and it is the first in China. A undergraduate student who posted a dissertation on FOCS later also won the FOCS Best Student Paper Award in 2019. It is already a very dazzling star in the theoretical computer field.

It can be said that Yao Ban has contributed huge to computer science.

As of December 2021, there were 358 papers published during the undergraduate period. There were 277 articles as the author or the main complete person, and 121 were in FOCS, STOC, SODA, NIPS, COLT, CVPR, AAAI, AAAI , ICLR and other top international conferences work reports.

This is curious, what kind of "mysterious organization" is it, can it be gathered so much "great god"?

The full name of Yao Ban is "Tsinghua Academy Computer Science Experimental Class". It belongs to the Tsinghua University Cross Information Research Institute (hereinafter referred to as the Cross Information Institute) and was founded by Academician Yao Yizhi.

The top elite class in the world is the Xueba of Xueba. Most of them are gold medals in mathematical competitions, physical competitions, and information competitions, or champions in college entrance examinations in each province, and join Yao Ban in a way to guarantee or independent enrollment.

Like Fan Zhiyuan, Li Jiatu, and Yang Tianqi, all three entered Tsinghua University in a guarantee method, and then selected into Yao Ban through layers. Among them, Fan Zhiyuan won the gold medal in the 34th National Youth Information Olympic Contest; Li Jiatu and Yang Tianqi won the gold medal in the 35th National Youth Information Olympic Contest.

In the Yao Ban, which was picked up by Wanli, there were Tsinghua Lili Students. All core courses were taught in English. It was easy to fall behind without making "desperate Saburo". The academic atmosphere here is very strong. Students learn from each other, and every corner of the bedroom may become a place for discussion and exchanges.

Fan Zhiyuan, Li Jiatu and Yang Tianqi are both the theoretical foundation, and they are interested in academic research. The three of them are very hard in Yao Ban. They believe that the best student thesis award this time, in addition to their own efforts, cannot be separated from the support and encouragement of a "master".

"Mr. Yao's influence on us is huge, he is like the lighthouse on the road of our way." Yang Tianqi said.

When he and Li Jiatu read a large number of domestic and foreign papers in the early stage, he was confused about the road he was walking. "At that time, I didn't know where to start. There was a bunch of knowledge in my mind, and my thinking was very chaotic."

The two gathered the courage to take the initiative to ask Academician Yao Zhizhi to talk. "Mr. Yao expressed his appreciation of us through reading the papers, and also pointed out that it is really difficult to find a problem that can be found directly as a novice."

"On the other hand, Mr. Yao believes that we have a certain knowledge reserve by our previous learning. We should try to solve some problems and accumulate research experience." Li Jiatu said, "Therefore, he suggested that we study 'explicit complexity. The question of the lower boundary. "

The suggestion immediately made the two of them shine. You know, this problem is very famous. This is the earliest and most fundamental problem in the field of circuit complexity.

Not only that, it is also a crazy problem in this field. From the 1950s to the present, there has been no fundamental progress about this problem, and many improvements in existing results are very complicated. The last time the issue was improved in 2016, and the last time was dating back to the 1980s.

Often the more complicated issues, the simpler the method. Because people do not have a fundamental understanding of this problem, the improvement of existing results may not depend on complex technology. It may be more needed for simple inspiration and detailed classification discussions.

"In other words, you don't need too much background knowledge. This is very suitable for novices like us." Yang Tianqi said. It is worth mentioning that the papers formed by Li Jiatu and Yang Tianqi's research on the issue were also accepted by this STOC. This has accumulated experience for them in the field of circuit complexity, and it is also a very important foundation to complete this best student paper.

The papers cooperated with Yang Tianqi and Yang Tianqi were accepted by STOC 2022. Picture source: Tsinghua University Cross Information Research Institute

"Mr. Yao is very satisfied with our results. He is the only Chinese who won the Turing Award. The Turing Award is the Nobel Prize in the computer industry. He can get his recognition and give us a lot of confidence. Continue to engage in scientific research. "Yang Tianqi said.

He quoted the words that idol brothers Chen Lijie said at the 2016 Tsinghua T also to express their ambitions.

"Mr. Yao once said that now it is the golden age of computer science, and it is also the golden age of all human beings! Born in such a golden age, I feel extremely honored. I dream of becoming a wave of waves in the wave of the golden age. Wisdom and bricks! "

Thesis link:

https://eccc.weizmann.ac.il/report/2021/125/

https://eccc.weizmann.ac.il/report/2021/023/

Reference link:

https://www.tsinghu.edu.cn/info/1175/94548.htm

https://iiis.tsinghu.edu.cn/index.php?v=Showcid=623id=5804

https://mp.weixin.qq.com/s/zlw7i-qmczbh8qpomlr8_q

https://zhuanlan.zhihu.com/p/60156478?utm_source=WECHAT_SESSIONUTM_MEDIUM=socialutm_oi=685086348583505920

https://mp.weixin.qq.com/s/q3wrczciufk_0F_FCNMC8W

editor | Fangyuan

Capture | Guo Gang

/> />