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.

1. 在理论计算里科学领域合作提出了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中的地位。

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，这一理论串联了诸多不同风味的学科，比如极值组合学，概率论，统计物理，分析学等等。

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.”

Wigderson的主要研究领域是理论计算机中的算法咬杂度等问题, 这一方面是我不太了解的。我听 说过的他的一个工作是关于expander graphs的构造。希望有了解的朋友可以来科普一下他的其他 工作。Quantamagazine的报道中也提到, Lovasz的工作更加驱动于数学问题, Wigderson的工作 更加驱动于计算机问题。

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

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

Categories: 未分类