The Abel Prize Laureates 2021

2021年的Abel奖于2021年3月17日公布

A joint statement on the announcement of the 2021 Abel Prize Laureates from the Embassies of Hungary, Israel, and the United States of America:

Today, the Abel Prize for 2021 was awarded to Professor László Lovász of the Alfréd Rényi Institute of Mathematics (ELKH, MTA Institute of Excellence) and Eötvös Loránd University, Hungary and Israel-born Professor Avi Wigderson of the Institute for Advanced Study, Princeton University, United States by the Norwegian Academy of Science and Letters.

They received this award for their “foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.”

We are proud to see the achievements and benefits that scientific research and international collaboration contribute to our global society and warmly congratulate both Abel Prize Laureates for winning this prestigious award.

总的来说，László Lovász的工作建立了组合数学与计算机科学之间的桥梁，提出了诸多原创性的方法论，并且解决了诸多重要的数学或理论计算机科学问题。我只能举一些我熟悉的例子，可能只是冰山一角。

1. 在理论计算里科学领域合作提出了LLL算法：其除了在几何领域的应用外，还在诸如数论，密码学领域发挥着巨大的作用。被认为是密码学家们最喜欢的算法。

我本人也非常喜欢LLL算法，不仅仅因为LLL算法在Akshay Venkatesh的2011年的文章A note on sphere packings in high dimension 中起到至关重要的作用，而这篇文章，也是目前人们知道的general的sphere packing问题的art of the tate lower bound(虽然离人们猜想的optimal的下界还差很远)，另一方面是因为LLL算法本质上就是将Euclidean算法和Random sampling结合起来，而我们知道通过Euclidean算法得到的逼近几乎就是人们可以构造出来的最好的逼近-continued fraction，因此LLL算法能在计算机复杂度理论和算法设计理论中大放异彩也是意料之中，因为在大部分情况下他几乎就是人们能够构造出来的最好的算法。

1. 在极值组合领域，给出了Local Lemma这一强力的工具，利用这一工具，有大量的问题被改进，例如大概一年前天才少年Ashwin Sah 的文章Diagonal Ramsey via effective quasirandomness就很好的利用了Local Lemma外加对于quasirandom structure很好的理解得到了对于对角附近的Ramsey数的下界的改进 Diagonal Ramsey via effective quasirandomness诸如对角Ramsey数的渐进下界，顺便一提Ashwin Sah感兴趣的研究领域非常广，他的计算能力非常强，有着精湛的概率技巧和不等式技巧，比如他轻松的用他的不等式技巧解决了好几个随机矩阵中的特征值的open problem，而他的另外一篇文章将张益唐用来处理孪生素数猜想的技巧和Sato-Tate conjecture的证明方法(处理方法是计算higher moment，很类似于概率中的生成函数法)结合起来。另一方面，后续的研究中，算法层面的Local lemma也是非常重要的。
2. 彻底解决了Kneser猜想，并且利用到了拓扑工具，令人震惊。
3. 在计算复杂度领域，给出了早期版本的PCP定理。
4. 在通信领域，彻底解决了五边形的香农复杂度，并且有以他名字命名的Lovász Theta function这样重要的工具。此工具在通信领域中的地位类似于feymann graph在quatum field theory中的地位。

关于Lovász Theta function

We begin with some background on perfect graphs. First, we define some quantities on graphs.
Definition 11.1. Given a graph $G$ on $n$ vertices, we define the following quantities:

1. The clique number of $G,$ written as $\omega(G)$, is the size of the largest clique in $G$.
2. The independence number of $G,$ written as $\alpha(G)$, is the size of the largest independent set in $G$.
3. The chromatic number of $G,$ written as $\chi(G)$, is the minimum number of colors required to properly color $G$.
4. The clique cover number of $G,$ written as $\bar{\chi}(G)$, is the size of the smallest clique cover in $G,$ which is the minimum number of vertex disjoint cliques such that every vertex is in some clique.

Recall that the complement of a graph $G,$ denoted $\bar{G},$ is the graph on the same vertices as $G$ such that two vertices are connected in $\bar{G}$ if and only if they are not connected in $G$. The following facts will be useful:

1. $\alpha(G)=\omega(\bar{G})$
2. $\chi(G)=\bar{\chi}(\bar{G})$
3. $\omega(G) \leq \chi(G)$
4. $\alpha(G) \leq \bar{\chi}(G)$
5. $\alpha(G) \chi(G) \geq n$

Lovász introduced a function $\vartheta$ satisfying $\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G)[?] .$ We begin by developing an SDP relaxation for $\bar{\chi}(G)$. We assign a unit vector $v_{i}$ to each vertex. If two vertices are in the same clique of the minimum clique cover, we would like their vectors to be the same. If two vertices are not in the same clique, we would like their vectors to be as far apart as possible. Note that when $k$ vectors are as spread out as possible, the dot product of any pair of them is $-\frac{1}{k-1}$. This means that if we have a clique cover of size $k$, there is an assignment of unit vectors to vertices such that every vertex in a clique is mapped to the same vector and, if two vertices are not in the same clique, the dot product of their vectors is $-\frac{1}{k=1}$. This is shown for clique covers of size $2,3,$ and 4 in Figure 11.4 .
LECTURE

THE LOVASZ $\vartheta$ FUNCTION

Assigning unit vectors to vertices such that the vertices in the same clique of the clique cover map to the same vector and vertices that are not in the same clique map to maximally separated vectors.
This suggests the following SDP relaxation:
where we use $i \sim j$ to denote that $(i, j) \in E(G),$ and $i \nsim j$ to denote that $(i, j) \notin E(G) .$ We can now define the Lovász $\vartheta$ function.

Definition 11.8. Given $G=(V, E), \vartheta(G)$ is the optimal value of the SDP in (11.3).
We can also write the following equivalent SDP:
$$
\begin{aligned}
\text { s.t. } &\left\langle v_{i}, v_{j}\right\rangle=t \quad i, j \in V, i \nsim j, i \neq j \
&\left\langle v_{i}, v_{i}\right\rangle=1 \quad \forall i \in V
\end{aligned}
$$
In this case, the optimum is equal to $\frac{1}{1-\partial(G)}$. For a graph that is a clique, $-\frac{1}{k-1}$ and $t$ both go to $-\infty$. Such graphs are not interesting to us, so this will not be a problem.

1. 在算法设计层面，参与设计了半正定规划的有效算法。
2. 发展了图极限理论，Yufei zhao关于Graph limit theory有一份精彩的Note，这一理论串联了诸多不同风味的学科，比如极值组合学，概率论，统计物理，分析学等等。

除了这些冰山一角的例子，László Lovász在极值组合，图论，理论计算机科学中还有有大量贡献，比如perfect graph conjecture的解决，在random walk领域的一系列工作等等。此外他也编纂了许多巨著，比如著名的习题集Combinatorial problems and exercises，以及Large network and graph limits。

很喜欢Abel奖对于他们的表彰：致他们对于理论计算机科学与离散数学的基础性贡献，以及他们将这些学科塑造为现代数学中心领域所发挥的主导作用。

They received this award for their “foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.”

如果说 Szemeredi 属于罕见的大器晚成型数学家，那么 Lovasz 就和大多数其他著名组合学家一 样, 属于天才少年。他高中时拿了三块 IMO 金牌, 并且 17 岁时就独立解决了图论中的重要问题。 关于他还有一个有趣的小故事：在当时的匈牙利, 除了博士学位 (Ph.D.) 外, 还有另一个学位 (C.Sc.) , 是一个由科学院授予的高于博士学位的学位。Lovasz大四那年, 由于他所在大学的规 定，即不允许本科生申请博士学位, 他先拿到了科学院授矛的C.Sc.学位, 也就是那个 “高于博士学 位” 的学位。转年，经过了一年的研究生学习后，他也拿到了博士学位。
从纯数学角度, Lovasz的很多工作基于概率方法。他自己在Abel奖专访里面也提到了这一点: 在过 去, 随机地去理解数学是一个很冷门的观点, 但是现在已经成为数学的很多领域中的核心思想之一
了。他说，就好像每个数学家都不应该惧怕 “函数” 这个概念一样，每个数学家都不应该惧怕用随 机的观点去证明数学问题。 (全部的专访内容详见youtube中the abel prize官方频道)
可能大家最熟知的他的工作是Lovasz Local Lemma, 早已经成为了教科书中的结果，在组合，群 论, 动力系统等方向均有很多应用。对于不了解的同学我稍微科普一下：假设有 $N$ 个 “坏” 事 件, 每个发生的概率是 $p$, 如果所有的事件都彼此独立，那么这些坏事全不发生的概率为 $(1-p)^{N}>0$ 。那么, 如果事件中存在一些事件不独立呢?
如果把每个事件看作一个点, 两个事件不独立代表两个点之间有一条边，那么所有事件彼此独立意 味着事件们对应的图是空图。Lovasz Local Lemma证明了，就算我们的图不是空图（即有一些事 件不独立于其他)，, 但是只要这个图足够稀疏，那么所有坏事件不发生的概率也可以 $>0$ 。
再稍微说一下我不太了解的Avi Wigderson。
Wigderson的主要研究领域是理论计算机中的算法咬杂度等问题, 这一方面是我不太了解的。我听 说过的他的一个工作是关于expander graphs的构造。希望有了解的朋友可以来科普一下他的其他 工作。Quantamagazine的报道中也提到, Lovasz的工作更加驱动于数学问题, Wigderson的工作 更加驱动于计算机问题。
阿贝尔奖专访中, Wigderson还被问到了他对 P/NP 问题的看法。Wigderson说，他相信这个问题 是可以被解决的, 他坚信 $\mathrm{P} \neq \mathrm{NP},$ 他同时也希望他有生之年可以看到这个问题被解决。
前一阵, Wigderson在给talk时，开玩笑的说了一句, 理论计算机学家，究竟是数学家还是计算机 学家?看来Abel 奖committee已经给了他回答。。
最后提一下, Lovasz和Wigderson两个人也是好朋友。下图是Szemeredi在2012年获得阿贝尔奖 时, Lovasz和Wigderson在会场互相交谈时的照片（来自quantamagazine)

除了数学之外，两位都是密码学领域的先驱级人物，LLL的L和GMW的W。

Lovász是格密码领域中格基约化算法LLL算法的提出者之一。

Wigderson是交互式证明和零知识证明领域的奠基者之一，和Goldreich, Micali 一起给出了理论上存在零知识证明解的有效范围——如果问题可以在多项式时间内验证解(NP问题)，就存在已知的零知识证明方案。具体做法主要是先将NP问题要证明的论断转化为NPC问题(例如SAT问题)的一个实例，由NPC问题的定义这样的规约一定能实现，然后利用已有的协议对NPC问题进行零知识证明，从而实现NP问题的零知识证明。

值得一提的是，基于格的密码/签名和零知识证明是当前密码学研究中非常重要且活跃的方向，除了nist正在征集的未来能抵抗量子计算机的加密/签名方案，还已经被用在了区块链技术和数字货币上。

---

内容参考了等待小蜗牛，yifan，Jamie Wen的知乎回答