※ 引述《ttucse ((((>(￣▽￣)<))))》之铭言：
: https://awards.acm.org/about/2023-turing
: 美国电脑学会ACM决定将资工最高荣誉颁给以色列的Avi Wigderson。
: "他重塑了我们对计算中随机性作用的理解以及数十年来在理论计算机科学领域的学术领导 地位而受到认可。
: " Wigderson是新泽西州普林斯顿高等研究院数学学院的赫伯特·H·马斯教授。
: 他是计算复 杂性理论、算法和最佳化、随机性和密码学、平行和分布式计算、组合学和图论以及理 论计算机科学与数学和科学之间的联系等领域的领导者。
: 四十年来他一直是理论电脑科学研究的领导者，他为理解随机性和伪随机性在计算中的作 用做出了基础性贡献。
: 电脑科学家发现随机性和计算难度（即识别没有有效算法的自然问题）之间存在显著的 关联。Wigderson与同事合作撰写了一系列极具影响力的关于用硬度换取随机性的著作。
: 他们证明在标准且广泛相信的计算假设下，每个机率多项式时间算法都可以有效地去随 机化（即完全确定性）。
: 换句话说，随机性对于高效率计算来说并不是必要的。 这一系 列作品彻底改变了我们对随机性在计算中的作用的理解，以及我们思考随机性的方式。
: 除了图灵奖，Wigderson还获得以下奖项:
: 1994 内万林纳奖(在电脑科学的数学方面有主要贡献者):表彰他在计算复杂性理论的工作
: 2009 哥德尔奖(理论计算机科学领域杰出论文):表彰他在图的锯齿积方面的工作
: 2019 高德纳奖(在计算机科学基础做出杰出贡献的人):表彰他对计算机科学在随机计算、 密码学、电路复杂性、证明复杂性、并行计算以及我们对图的基本性质的理解所作的贡献
: 2021 阿贝尔奖(数学界诺贝尔奖):表彰他对理论计算机科学和离散数学的基础性贡献，以 及他们将其塑造为现代数学的中心领域方面的领导作用
首先先介绍一种东西叫做逻辑闸，例如AND逻辑闸呢，就是输入有两根电线，两根电线
都可以承载一个0或1的值，如果两根电线都是1，这个逻辑闸才会输出1，否则就输出0，
其它种逻辑闸就不赘述了。
有些计算问题被相信无法用小型电路解决，也就是你如果要用逻辑闸构成一个电路，
来解决这种问题，将会需要很多个逻辑闸才能办到，这种信念叫做circuit lower
bound，是计算理论的大哉问，除了少数几个知名的例子外，一般相信circuit lower
bound极难被证明。
另外一种问题是derandomization问题，也就是说如果你有一个会丢骰子的算法可以
解决某种问题，是不是就一定可以换一个不用丢骰子、且执行时间也差不多的算法，
来解决同样的问题？这也是极难回答的。
Wigderson参与的一些研究证明了circuit lower bound跟derandomization问题本质上
是同一个问题，大概就4这样。
不过当然，两种问题都仍然是没有人会回答的，只是知道两者差不多等价。
南无阿弥陀佛。