159 “图灵测试”161（1 / 2）
接下来，我们把目光转向去年的的图灵奖得主，新泽西州普林斯顿高等研究院（IAS）的阿维·维格德森（AviWigderson），他以跨越多个学科的工作而闻名，ACM在23年图灵奖的完整通告中提及的Wigderson的有三篇代表作:
“Hardnessvs.Randomness”(co-authoredwithNoamNisan
“BPPHasSubexponentialTimeSimulationsUnlessEXPTIMEhasPublishableProofs”(co-authoredwithLászlóBabai，LanceFortnow，andNoamNisan
“P=BPPifERequiresExponentialCircuits:DerandomizingtheXORLemma”(co-authoredwithRussellImpagliazzo)
（计算理论领域的领导者是图灵奖的最新获得者，该奖有时被称为计算机科学的“诺贝尔奖”）
Wigderson此前于21年获得了数学中最高奖项之一的阿贝尔奖，图灵+阿贝尔的含金量，足以证明这位是绝对的大牛。
他是普林斯顿高级研究院数学学院的
HerbertH.Maass的教授。
他在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等领域均有突出贡献，并且在理论计算机科学与数学及科学的交叉领域中，也具有重要影响。
在过去几十年里，Wigderson对于理解计算中的随机性和伪随机性，做出了开创性贡献。
在此前，已经计算机科学家们已经发现，随机性与计算难度之间存在显著的联系，比如，一些自然问题并没有高效的算法解决方案。
而Wigderson和他的团队，他们成功地证明了，在一些广泛认可的计算假设下，所有的概率多项式时间算法”，都可以被有效转化为确定性算法。
也即是说，高效的计算并不依赖于随机性。
从此，我们对于计算中随机性作用的理解被彻底改变。
'P=BPPifERequiresExponentialCircuits:
DerandomizingtheXORLemma”(与RussellImpagliazzo合著)
这篇论文介绍了一种更强的伪随机发生器，它在本质上实现了难度与随机性之间的最优权衡。
'BPPHasSubexponentialTimeSimulatUnlessEXPTIMEhasPublishableProofsj(与LászlóBabai.LanceFortnow和NoamNisan合著)
这篇论文利用“难度放大”，证明了在弱假设下，可以在亚指数时间内模拟无限多输入长度的有限错误概率多项式时间（BPP）。
TP=BPPifERequiresExponentialCircuits:DerandomizingtheXORLemma”(RussellImpagliazzo合著）
这篇论文介绍了一种更强的伪随机发生器，它在本质上实现了难度与随机性之间的最优权衡。
Wigderson的这三篇论文，其理论被广泛应用于理论计算机科学的多个分支，并且激发了多位专家的重要研究。
在计算中随机性的广泛领域内，Wigderson与OmerReingold、SalilVadhan和MichaelCapalbo合作，首次高效构造了展开图，这些图具有出1稀疏性和连通性，广泛应用于数学和理论计算机科学中。
Wigderson的相关工作主要从两个方面出发，一是如何用很少的随机性来模拟大量“不可区分“的随机性，二是将去随机化和线路复杂性下界建立联系
先说第一类结果.在这里我们把随机抛掷的硬币的结果(正反面)称作随机比特.Wigderson与HUJI的同事NoamNisan一道在八十年代末(即ACM图灵奖通告中第一篇代表作)，证明了如果存在足够好的伪随机生成器(pseudorandomgenerator，PRG)，
那么可以导出上述去随机化成立.这里的PRG就是在设法用足够少的随机比特来生成足够多的“不可区分“的随机比特--注意到如果随机比特足够少如对数多个)的话，我们可以通过遍历所有结果来模拟
第二类结果则是在线路复杂性下界(circuitlowerbound)和退随机化(derandomization)之间的建立联系.直觉想法是说，如果一个结果“难“(hardness)算出来的话，那么直觉上这个结果看起来应该很“随机“(randomness).ACM图灵奖通告中后两篇代表作就给出了上述直接想法的量化描述:
Wigderson与Babai，Fortnow和Nisan(1991)证明了如果指数时间的确定性算法(EXP)最坏情况下都需要指数规模线路的话，那么BPP内的计算都可以被准多项式时间的确定性算法模拟
Wigderson和Impagliazzo(1997)的进一步改进则证明了如果线性指数时间的确定性算法(E)最坏情况下需要线性指数规模的线路的话，那么BPP=P
这一类工作的另一视角则是用去随机化导出线路复杂性下界
在1994年的一篇论文中，Wigderson与计算机科学家NoamNisan共同证明——