|
马克·布雷弗曼（Mark Braverman）的职业生涯一直在将棘手的问题转化为信息复杂性的语言。
作者：Stephen Ornes 2022-7-5 译者：zzllrr小乐 2022-7-5 到他 17 岁时，马克·布雷弗曼已经在三个国家生活过，并且会说同样多的语言。但尽管没有家乡，但他很快就把理论计算机科学称为自己的家。“理论计算机科学就是你想要的任何东西，”他在普林斯顿大学通风良好的办公室里说道，他坐在一块写满数学方程式的白板和一堵装饰着家庭照片的墙壁之间。 十多年来，38 岁的布雷弗曼一直在开发一种具有变革意义的交互通信的新理论，扩展和丰富了克劳德·香农八十年前开始的开创性工作。布雷弗曼不断发展的框架允许研究人员将“信息”和“知识”等抽象概念转化为精确的数学术语。因此，他们可以将难题重铸为更精确的陈述。该计划带来了对计算局限性的新见解，并直接说明了人们在线互动的方式。 对于这一成就和其他成就，IMU国际数学联盟授予布雷弗曼 IMU算盘奖章，该奖章被广泛认为是计算机科学家可以获得的最高荣誉。（该奖项以前称为内万林纳奖，但在历史学家指出该奖项的芬兰研究人员是纳粹认同者后重新命名。）算盘奖章每四年颁发一次，获奖者必须是40岁以下。 IMU 的获奖引文指出，布雷弗曼对信息复杂性的贡献使人们更深入地了解了两方相互通信时不同的信息成本衡量标准。他的工作为不易受传输错误影响的新编码策略以及在传输和操作过程中压缩数据的新方法铺平了道路。 “获得这种认可显然很棒，它可能会更容易推出新事物，”布拉弗曼说，他在一月份获悉该奖项。但他也很快否定了他是一个孤独的天才的想法。“有很多非常有才华的人，”他说，并补充说这个领域很小，但充满了有天赋的思想家和富有成效的合作。 布雷弗曼在普林斯顿的同事、数学家Assaf Naor称 布雷弗曼 是“无所畏惧”的问题解决者。“他非常好奇、博大精深、喜欢冒险，”Naor 说。“当你拿着一把大锤子时，一切看起来都像钉子。马克开发并了解了计算机科学理论——这是一把相当大的锤子。” 数学奇迹 布雷弗曼是一位数学家母亲和一位物理学家父亲的儿子，他于 1984 年出生在俄罗斯彼尔姆市，这是一个靠近乌拉尔山脉西坡的工业城市。随着苏联解体及其引发的不稳定，1992 年，他 8 岁时，这个年轻的家庭搬到了以色列的海法。 虽然他一直被数学和计算机编码所吸引，但 布雷弗曼 说他的父母从不强迫。“他们让我对数学感到满意，”他说。他还表现出早期的学科天赋，在 1998 年、1999 年和 2000 年的国际数学奥林匹克中获得了两枚铜牌和一枚金牌。在海法理工学院，他于 2001 年春季获得了数学和计算机科学双学位。那年晚些时候，他的家人搬到了加拿大，他的母亲在那里获得了卡尔加里的教职任命。那年冬天，他开始在多伦多大学攻读计算机科学研究生。他当时只有 17 岁。
布雷弗曼最喜欢思考的地方是他办公室的沙发。他思考的许多问题都涉及量化难题的难度。 “无论你是什么年龄，都很难移动，”他说。然而，他的旅行提供了更大的世界观。“你没有家，但你明白有多种文化，”布拉弗曼说。“你可以告诉来自一种文化的人们另一种文化的基本概念。” 他不只是在谈论地理：他说，理论计算机科学是一个特别好的地方，可以让来自不同知识领域的想法找到共同语言。他获得的奖项包括欧洲理论计算机科学协会的普雷斯伯格奖和美国国家科学基金会的沃特曼奖，这些奖项的嘉奖说明经常指出他的工作在其他领域的深远应用。 他的毕业作品就是一个很好的例子。早在他在多伦多的时候，布雷弗曼 就对 Julia 集感到好奇，Julia 集是产生令人眼花缭乱和复杂的分形图形的点的集合，这意味着当你放大时，你会看到相同的模式出现。 要找到给定多项式函数的 Julia 集，只需输入一个点以找到输出值，然后将该输出值插回函数中。一遍又一遍地运行这个过程——使用输出作为输入——可以揭示点如何随着迭代而演变。一些起点会产生重复的数字序列，但其他起点只会变得更大；这些逃到无穷远。绕轨道运行的点与它们开始位置相当接近的点与逃逸到无穷远的点之间的边界会产生扭曲、复杂的形状。这些形状是函数的 Julia 集。它们在动力系统的数学领域中占有重要地位，该领域侧重于系统如何随时间演变。 只是，布雷弗曼不在动力系统领域。他是计算机科学专业的一名十几岁的研究生。Julia 集通常不是课程的一部分。然而，他的导师斯蒂芬·库克（Stephen Cook）和多伦多大学的数学家迈克尔·扬波尔斯基（Michael Yampolsky）指导布雷弗曼之前通过计算机科学的眼光观察Julia集。该研究从复杂性的角度描述了分形，该框架（除其他外）寻找将可以在合理时间内解决的难题与只能近似解决的超级难题区分开来的基本规则。在 Julia 集中，布雷弗曼 遇到了类似的描述：什么规则和函数将靠近的点与逃到无穷远的点分开？ 这是看待问题的成熟方式。“他在学术上很年轻，但也比同龄人年轻很多，”Yampolsky 说。“和这么年轻、这么聪明的人一起工作很有趣。他拥有这种智力上的成熟，更像是同行。” 布雷弗曼 通过思考基本机制开始了他对分形的研究：在计算方面，是什么让 Julia 集特别？大部分工作是由美国数学家约翰·米尔诺（John Milnor）建立的，现在在石溪大学。布雷弗曼 在 Cook 的指导下并与 Yampolsky 合作，研究了 Milnor 的策略，并开始专注于计算异常困难的集合，例如需要多次迭代才能揭示它们是保持接近还是逃逸到无穷大的复函数。与库克一起，布雷弗曼调查了以前的模型，这些模型提供了什么时候可以计算以及什么时候不能计算的规则。随着时间的推移，研究人员开始怀疑：某些函数是否会如此复杂以至于根本无法计算它们的 Julia 集？ 这就是计算机科学的观点被证明是无价的地方。那种问题——有没有我们不能解决的问题，我们能证明吗？——是典型的理论计算机科学。在动力系统中，一个由数值模拟驱动的领域，它近乎异端。 “直觉是它们可能很难计算，但都是可行的，”Yampolsky 说。“也许你只需要等待很长时间才能看到这张照片，但没有任何实际障碍。”
到 17 岁时，布雷弗曼已经在三个国家生活过，会说三种语言。“你没有家，但你明白有多种文化。” 布雷弗曼 和 Yampolsky 联系了 Milnor，后者对动力系统的计算机科学方法感到兴奋，并提供了反馈。多年来，该小组一直在戳戳这个奇怪的问题，寻找方法来证明无法找到某些 Julia 集——这本来就很难证明。但在 2005 年，受到一个法国小组的发现的启发，布雷弗曼 和 Yampolsky 找到了前进的道路，打破了研究人员的直觉。他们发现对于某些函数，Julia 集不仅难以计算，而且被证明是不可能的。 “这是数学奇迹之一，”Yampolsky 说。“还有一点震惊。” 动力系统社区最初反对这个想法。“但有时数学思想需要时间（才能被接受），你知道吗？” 他们的第一篇论文为可计算的 Julia 集制定了明确的规则，并提出了一种算法来查找无法计算集的函数。这一发现导致了大量的结果。Yampolsky 说，最令人震惊的事情之一是证明他们找到不可计算的 Julia 集的方法实际上是唯一的方法。这项研究首先为 布雷弗曼 的硕士论文奠定了基础，然后为他在多伦多的博士工作奠定了基础。他与 Cook 的论文描述了用于研究 Julia 集的计算模型，最终他和 Yampolsky 撰写了一本关于该主题的书，于 2009 年出版。 布雷弗曼说，当他开始这项工作时，“这是一个有点过时的领域”，但这并没有打扰他。他说：“在计算机科学领域，这就是一个问题想法刚刚好的区域。” “如果太容易了，结果就会泛滥成灾。如果太难，它就会变得如此稀少，以至于人们失去兴趣，你就无法维持一个社区。” 数学乐观主义 在读研究生期间，布雷弗曼建立了另一个重要的联系——这次是与一位名叫安娜的研究生同学、未来的心理学家和他未来的妻子。她也出生在俄罗斯，巧合的是，在海法的同一所小学里，她比布雷弗曼晚一年。“我们实际上从来没有说过超过一个字，”布拉弗曼说。但两个家庭最终都搬到了加拿大，马克和安娜再次相遇——这一次有更多的话——并于 2007 年结婚。 获得博士学位后，布雷弗曼花了更多时间旅行和建立联系。他首先在普林斯顿的高级研究所呆了一个月，在那里他遇到了理论计算机科学家 Anup Rao，将与他一起稳定工作多年。之后，他在马萨诸塞州剑桥市的微软新英格兰研究院担任了两年的博士后研究员。在微软之后，布雷弗曼回到加拿大，在多伦多大学任教一年。 在寻找刚刚好的问题的过程中，他参与了各种项目，从医疗保健数据挖掘到未解决的关于随机性的数学问题。普林斯顿大学的数学家 Naor 说，布雷弗曼 喜欢直接陷入棘手的问题。“假设你面前有一块巨石，很长一段时间以来，人们一直试图绕过这块巨石，”Naor 说。然后有人出现并制定了解决它的计划。如果它不起作用，这个人会找到另一个计划，然后是另一个。Naor 认为，这种精神表现出一种根深蒂固的乐观主义。“如果你不乐观，你就永远无法绕过那块巨石，”他说。“马克有。”
布雷弗曼 自 2011 年以来一直在普林斯顿，比他在其他任何地方居住的时间都要长。 他于 2011 年加入普林斯顿大学。安娜以临床心理学家的身份加入该大学，这对夫妇在距离计算机科学大楼三个街区的地方买了一栋房子。在这一点上，他的家比其他任何地方都要久。他们将继续生两个孩子——一个在 2016 年，另一个在 2018 年。 定居新泽西后，布雷弗曼 开始从事信息复杂性领域的工作，这是 Rao 在 2008 年将他介绍给他的领域。信息复杂性从更大的信息论学科中衍生出来，这始于 1948 年 Claude Shannon（克劳德·香农，已故数学家、信息论学家，zzllrr译注）的开创性工作制定了一个人通过渠道向另一个人发送信息的数学框架。那篇论文试图量化信息，并向世界介绍了“比特”的概念，作为其基本的、保守的单位。香农写道，根本的挑战是以精确或接近精确的精度将数据从一个点传递到另一个点。如果数据包含一些“简单”的东西，比如随机数字流，并且通道是无噪音的，那就很容易了。 但是，如果这些数据具有复杂的统计关系（例如英语中的数十万个单词）或信道嘈杂，那么任务很快就会变得棘手。借用统计力学的工具，香农将数据压缩的概念形式化，并将“熵”的概念改编为与消息中信息量相关的量。布雷弗曼说，他的关键见解是将信息本身的熵与信道的容量——信息发送的速率——区分开来。在这些条件下，只要消息的熵不超过通信信道的容量，就可以执行通信任务。这个想法自然地提出了另一个问题：通过通道发送消息所需的最少熵是多少？ 布雷弗曼在普林斯顿的第一批博士生之一，耶路撒冷希伯来大学的理论计算机科学家Omri Weinstein说：“香农表明，如果对话是单向的，只有一方发言，那么你可以优化压缩数据，”这意味着尽可能少的熵。 香农正在考虑嘈杂的电话线。布雷弗曼专注于将香农的工作扩展到单向传输之外。特别是，他不仅想考虑如何发送数据，还想考虑如何共享和操纵数据，例如通过算法。他可以看到香农的想法可以应用于通信复杂性领域的方式，它问：计算的通信成本是多少？这个问题更贴切地反映了互联网上每天发生数十亿次的情况：两方，例如买方和卖方，相互通信以完成某些交易。他们只关心结果——知道付了多少钱，付给谁——而不是他们如何到达那里。实现该目标可能需要反复来回传递信息。布雷弗曼看到信息论的形式主义可以适应这种情况，但它会很复杂。这种交流的基础是什么数学？起初，这个挑战提出了一系列离散的、可接近的问题，与香农最初探索的单向情况不同。 “最初我的动机是解决一些问题，但我更喜欢建立理论，所以结果证明有一个理论要建立，”布雷弗曼说。建立理论意味着解决问题、设计证明、寻找与其他领域的联系以及招募研究生来提供帮助。“在接下来的 10 年里，我花了很大一部分时间来研究它。” 寻找答案 布雷弗曼 最大的贡献是建立了一个广泛的框架，该框架阐明了描述交互式通信边界的大而通用的规则——这些规则为通过算法在线发送数据时提出压缩和保护数据的新策略提出了新的策略。 以前的研究人员研究了两个人如何来回发送信息，特别是在一个人可能什么都不知道或者他们没有重叠信息的简单情况下。在 1970 年代，计算机科学家研究并解决了如果两个人一开始就有一些重叠信息会发生什么情况。但 布雷弗曼 和他的合作者首先证明这些交换是计算任务，而不是数据传输任务。 例如：想象两个人每个人都有一个动物列表和一个协议，这是一种来回发送消息的方式。他们想确定他们有哪些共同的动物，如果有的话，以及要弄清楚这一点需要付出多少努力。在这种情况下，每个人都有一些信息开始（他们知道他们在谈论动物），并且每条消息都会添加到该信息中。信息的增加与以比特为单位的通信成本有关，布雷弗曼 和 Rao 在 2011 年的一篇论文使这种联系比以往任何时候都更加紧密。
通过他的工作，布雷弗曼为我们理解多方之间的通信（例如在线商务）的方式带来了数学上的严谨性。 这一证明使他们对沟通产生了其他见解，包括一个称为直和问题的问题版本。它涉及成本问题：解决一个问题的多份副本是否与解决一次并乘以重复次数具有相同的通信成本？还是有“批量折扣”？在数据传输的情况下，直和成立。但 布雷弗曼 和 Rao表明，对于交互式情况，该问题相当于一个看似无关的问题，称为“交互式压缩”问题。这问如果两个人交换一百万条短信但只学习 1000 位信息，是否可以将交换压缩为 1000 位？使用 布雷弗曼 和 Rao 的工作，研究人员已经证明答案是否定的。 信息论和计算复杂性之间的这种联系也促使 布雷弗曼 在两个或更多人之间共享数据时寻找优化数据压缩的新方法——这是在线通信的核心。在 2011 年至 2020 年期间，布雷弗曼 和他的合作者描述了压缩两方或多方之间共享信息的数学规则。这项工作引发了其他问题；例如，他还与他的合作者和学生一起研究了对话类型如何引发沟通成本。 布雷弗曼不仅破解了这些问题。他引入了一种新的视角，允许研究人员首先将它们表达出来，然后将它们翻译成数学的正式语言。布雷弗曼 的理论为探索这些问题和确定可能出现在未来技术中的新通信协议奠定了基础。 “这是一个非常强大的理论，” 1994 年获得内万林纳奖的高等研究院理论计算机科学家Avi Wigderson 说， “这是香农工作的美丽、丰富和复杂的延伸。” 尽管布雷弗曼在他以前的学生和博士后推动该理论的过程中继续指导该理论，但他的大部分工作已经完成。现在他的兴趣更多地集中在一个称为机制设计（mechanism design）的新领域，该领域使用经济学和博弈论的数学方法。他最近还与 Naor 在构建称为Lipschitz李普希兹函数推广的东西的长期挑战方面取得了进展，这是经典分析和几何中的一个问题。 “他确实带来了计算机科学的见解，这与我长大的方式非常不同，”Naor 说。“他的观点与我的想法不同。但这也是一种直觉和观点。他有一种他已经发展起来的哲学，一种他带来的观点。” 赢得算盘奖章不会改变这一切。如果有的话，布雷弗曼对数学的广泛好奇心多年来加深了，这支持了他毕生的论点：解决棘手的问题实际上就是找到合适的语言来研究它们。在其他学科中并非如此：你不能只是偶然发现 Alpha半人马座，或意外发现 Covid-19 疫苗。巨大的进步通常需要技术和多年的增量进步。但在数学和计算机科学中，大解决方案可能就在附近，隐藏在一种未破译的语言中。 “你基本上会觉得自己一无所知，但在解决问题的五分钟内就完成了，”他说。这就是他想传授给他的学生和数学继承人的东西。他说，像算盘这样的大奖项“是一种责任。它使你成为大使。这让学生们明白，这些并不是完全疯狂的想法。” 原文链接： https://www./mark-braverman-wins-the-imu-abacus-medal-20220705/ |
|
|
