Avi Wigderson： 探索随机性的力量和局限
2024-04-12
本文介绍了2023年ACM A.M. 图灵奖获得者Avi Wigderson的主要工作。Wigderson对计算复杂性理论做出了持久贡献，他的研究兴趣包括密码学、优化、随机性、伪随机性和电路复杂性等。他关于零知识证明的研究表明，任何具有证明的陈述都可以以不透露任何额外信息的方式向他人证明。此外，他还证明了在标准计算假设下，每个高效的随机算法都可以完全去随机化，这意味着随机性对于高效计算来说并非必要。近年来，Wigderson一直致力于非交换优化，将欧几里得空间中的凸优化工具扩展到更一般的黎曼流形环境。
48