破解随机性“密码”的人
创始人
2024-04-12 02:17:50
0

原标题:破解随机性“密码”的人

抛起一枚硬币,落地时哪一面会朝上?多数人认为“看运气”“五五开”。

真是如此吗?面对这一经典场景,美国普林斯顿大学教授维格德森(Avi Wigderson)指出,抛硬币或掷骰子,并不是真正随机的:如果你有足够的关于物理系统的信息,那么结果是完全可以预测的。完美的随机性是难以捉摸且难以验证的。

30年前形成的这一理论,彻底改变了计算数学对随机性的理解,对计算机科学的进步影响至深。

4月10日,有“计算机界诺贝尔奖”之称的图灵奖2023年获奖名单揭晓,花落维格德森。理由是他对计算数学基础的贡献,包括重塑人类对计算中随机性作用的理解,以及数十年来在理论计算机科学领域的领导地位。

图灵奖是计算机科学领域的最高荣誉。除了图灵奖之外,维格德森还与另一位学者分享了2021年的阿贝尔奖(Abel Prize),该奖项是数学界的最高荣誉。他也是唯一一位同时获得阿贝尔奖和图灵奖的人。

数学是计算机科学的基础

颁发图灵奖的美国计算机协会(ACM)主席雅尼斯·约安尼迪斯(Yannis Loannidis)在该组织发布的一份声明中表示:“数学是计算机科学的基础,维格德森的工作将广泛的数学子领域与理论计算机科学联系起来。”

维格德森因其在计算复杂性理论方面的工作而闻名,他主要研究随机性在计算中的作用。在上世纪90年代的一系列极具影响力的论文中,维格德森及其同事证明了计算在没有随机性的情况下也可以同样高效,并从那时起就塑造了算法设计。他的研究还包括协议设计和密码学,奠定了当今大部分数字基础设施的基础。

普林斯顿大学数学系教授许晨阳对第一财经记者表示:“维格德森做的领域属于计算复杂度,是数学和计算机交叉的领域。这些年他在纯数学领域的影响力也越来越大。”

计算复杂性理论所研究的,是资源中最常见的时间(要通过多少步才能解决问题)和空间(在解决问题时需要多少内存),或者在并行计算中需要多少并行处理器才能解决问题。

维格德森于1999年加入普林斯顿高等研究院(IAS),并在那里建立了计算机科学和离散数学项目。在普林斯顿高等研究院的采访中,维格德森表示,自己既是一位数学家也是一位计算机理论科学家,研究的是计算领域的数学基础。

上世纪70年代,维格德森在以色列海法大学开始了大学生涯。最初他主修数学,但在父母的建议下转向了计算机科学。他的父母认为,这个专业更好找工作。

虽然未学成数学专业,但维格德森很快就发现,计算机科学是一个充满未解之谜的领域,而这些谜题,本质上都与数学相关。他早期的一项开创性工作,正是探讨一个看似矛盾的问题:能否在不展示证明过程的情况下让人相信,一个数学命题已经得到了证明?

在数学和计算机科学交叉领域的一系列发现中,维格德森的研究巩固了所谓的“零知识证明”理论,这在密码学和数字安全中至关重要。今天,零知识证明(Zero-Knowledge Proof,ZKP)技术已融入了隐私、合规性、身份验证和区块链技术等现代应用中。

普林斯顿大学计算机科学家拉齐(Ran Raz)评价维格德森称:“Avi在密码学领域有许多极其重要的成果,最重要的理论就是零知识证明。”

维格德森影响深远的论文包括:《Hardness vs. Randomness》(《对抗性与随机性》,与诺姆·尼桑(Noam Nisan)合著)。这篇论文介绍了一种新型伪随机发生器,并证明了在比以前已知的假设更弱的条件下,可以对随机算法进行高效的确定性模拟。

维格德森这些理论的影响远远超出了随机性和去随机化领域,被应用于理论计算机科学更广泛的领域,且激发了该领域多位领军人物发表具有影响力的论文。

他的工作融入今天人们的日常生活

菲尔兹奖首位华人得主丘成桐对第一财经记者表示,维格德森获得图灵奖并不意外,因为与其称他为一位数学家,维格德森更是一名计算机学家,他的主要研究领域是计算机方面的工作。“当然数学是一切科学理论的基础。”丘成桐表示。

理论计算机科学专注于计算领域的数学基础,理论计算机科学还致力于设计高效的算法。事实上,每一项触及我们生活的计算技术都是通过算法实现的。深入理解构成强大和高效算法的原理,不仅能增进人们对计算机科学的认识,还能帮助人们更好地理解自然规律。

随机性基本上是一种在不知道最优解的情况下,确保对最优解有正确了解的方法。随机性在计算机科学中找到了无数其他用途,从密码学到博弈论到机器学习。

值得关注的是,2017年谷歌向普林斯顿IAS注资,开始研究新的机器学习的方法。谷歌高级副总裁Jeff Dean表示,维格德森的研究几十年来“奠定了理论计算机科学的发展进程”,而他的工作也直接融入了人们的日常生活。

第一财经记者注意到,去年11月,受2000年图灵奖得主、清华大学交叉信息研究院院长姚期智邀请,维格德森刚刚到访过清华大学交叉信息研究院,进行了“模仿游戏”源流和应用的学术讲座。

姚期智当时在介绍维格德森时说道:“我和维格德森已经相识40多年,都从事计算机理论研究,Avi在理论方面已形成了独到洞见。”

姚期智的研究方向包括计算理论及其在密码学和量子计算中的应用。他用计算机发牌、打牌,研究计算机理论,并将这种理论应用到密码学。用通俗的比喻来讲,生意合伙人如果互相发送电子邮件,即便使用只有双方通晓的暗语,也存在泄密的可能,这就牵涉到信息安全和加密,这些方向与维格德森的研究也高度重合。

在去年11月的那场报告中,维格德森从阿兰·图灵提出“图灵测试”出发,叙述了“模仿学习”理论在密码学、随机性、离散数学、数论等领域的现代应用。他基于凯撒密码(Caesar’s Cipher)、恩尼格玛密码机(Enigma machine)、选举(secure elections)等案例,引导学生思考安全性的定义、随机性的应用、隐私和效用的平衡等问题。

他还回应了AI大型大语言模型出现后,会对理论计算机研究的发展方向产生什么样的影响。对于理论计算机研究将如何应对人工智能发展这一问题,维格德森表示:“尽管包括大语言模型在内的人工智能有很多惊人表现,但最重要的问题是AI还有哪些是不能做的。我相信人工智能发展过程中总有天花板。”

维格德森还称,自己曾为解决一个开放性问题花了40年时间,并建议学生要选择自己喜欢的研究领域,享受在失败中不断学习的过程,这样才能在科研道路上走得长远。

相关内容

热门资讯

浩利丰取得一体式紫铜消音器专利... 金融界2025年7月11日消息,国家知识产权局信息显示,武汉浩利丰机械有限公司取得一项名为“一种一体...
人保再保发布行业首个《新能源汽... 2025年6月,在人保再保险股份有限公司第五届“技术引领,共创未来”技术论坛上,公司正式发布了行业首...
SpaceX第七次载人飞行Cr... 2025-07-11 09:20:55 作者:狼叫兽 NASA 与 SpaceX 近日正式宣布,...
我科研团队首次实现小鼠全身神经... 来源:科技日报 科技日报记者 吴长锋 记者10日从中国科学技术大学获悉,该校毕国强教授、刘北明教授联...
从“实验室”走向“生产线” 全... 封面新闻记者 伍雪梅(主办方供图) 7月10日,“长江首城宜创汇”协同创新大赛人工智能专项赛总决赛在...
正海磁材:人形机器人等领域有望... 今年以来,随着机器人行业的快速发展,作为上游原材料的稀土永磁行业也备受市场关注。 日前,正海磁材(3...
原创 百... 2024年,我选定一个题材,用100台国产老相机拍摄100个胶卷。然后把相机送给有缘人(也就是进入我...
淄博:三大赛道支撑装备制造业突... 回首过往,淄博制造的金字招牌熠熠生辉,在深厚工业底蕴的滋养下,淄博装备制造业这个已有百年底蕴的产业,...
航宇科技获得实用新型专利授权:... 证券之星消息,根据天眼查APP数据显示航宇科技(688239)新获得一项实用新型专利授权,专利名为“...
真相来了|网传太阳能板释放有害... 央视网消息:国家统计局数据显示,2024年,我国太阳能电池产量达6.8亿千瓦,同比增长15.7%。日...
消息称黄仁勋下周到访中国:特供... 来源:快科技 快科技7月11日消息,H20被禁止向中国厂商禁售后,黄仁勋可能是最着急的人,不过现在看...
叮当健康智能售药机进驻中央民族... “这个24小时售药机真是太方便了“,中央民族大学(丰台分校)一名正在自助购药的学生表示。 日前,在北...
西樵做小程序的公司 在当今数字化快速发展的背景下,小程序作为一种轻量级的应用工具,已成为许多企业和个人实现业务拓展、提升...
123 光年外的天枢星,人类未... 朋友们,咱今儿聊聊北斗七星里的天枢星。这星星可有些年头了,大概 2.8 亿年前就诞生啦,离咱们地球约...
全球最快!中国科大首次实现 记者7月10日从中国科学技术大学获悉,该校教授毕国强、刘北明联合合肥综合性国家科学中心人工智能研究院...
检索增强生成(RAG)为何在今... 在 人工智能领域,有一种名为检索增强生成(RAG)的方法正在成为帮助模型获得精准结果的关键途径。 ...
韩媒感叹:全球百大顶尖人工智能... 【CNMO科技消息】近日,韩媒援引最新研究表示,全球前100名顶尖人工智能(AI)科学家中,半数为中...
智创未来|我校与网易互娱SON... 7月9日上午,网易互娱音频总监吴盛强一行赴我校调研交流,我校党委副书记、院长陶陌出席座谈会。 陶陌...
“空中的士”要来了!温州苍南“... 7月9日,“峰飞航空科技(苍南)展示体验中心” 正式启用,标志着温州市苍南县在打造浙南低空经济产业基...
世运电路获得实用新型专利授权:... 证券之星消息,根据天眼查APP数据显示世运电路(603920)新获得一项实用新型专利授权,专利名为“...