开发出一种理解沟通的新方法的科学家

“无论你是什么年龄，都很难移动，”他说。然而，他的旅行提供了更大的世界观。 “你没有家，但你明白有多种文化，”布拉弗曼说。 “你可以告诉来自一种文化的人们来自另一种文化的基本概念。”他不只是在谈论地理：他说，理论计算机科学是一个特别好的地方，可以让来自不同知识领域的想法找到共同语言。他获得的奖项——包括欧洲理论计算机科学协会的普雷斯伯格奖和美国国家科学基金会的沃特曼奖——的引用经常指出他的工作在其他领域的深远应用。

他的毕业作品就是一个很好的例子。在多伦多的早期，Braverman 对 Julia 集产生了好奇，Julia 集是产生令人眼花缭乱和复杂的分形图形的点的集合，这意味着当你放大时，你会看到相同的模式出现。

要找到给定多项式函数的 Julia 集，只需输入一个点以找到输出值，然后将该输出值插回函数中。一遍又一遍地运行这个过程——使用输出作为输入——可以揭示点如何随着迭代而演变。一些起点会产生重复的数字序列，但其他起点只会变得更大；这些逃到无穷远。绕轨道运行的点与它们开始位置相当接近的点与逃逸到无穷远的点之间的边界会产生扭曲、复杂的形状。这些形状是函数的 Julia 集。它们在动态系统的数学领域中占有重要地位，该领域侧重于系统如何随时间演变。

只是，布雷弗曼不在动力系统领域。他是计算机科学专业的一名十几岁的研究生。 Julia 集通常不是课程的一部分。然而，他的顾问斯蒂芬库克和多伦多大学的数学家迈克尔扬波尔斯基指导布雷弗曼之前通过计算机科学的眼光观察朱莉娅的工作。该研究从复杂性的角度描述了分形，该框架（除其他外）寻找将可以在合理时间内解决的难题与只能近似的超难题区分开来的基本规则。在 Julia 集中，Braverman 遇到了类似的描述：什么规则和函数将靠近的点与逃到无穷远的点分开？

这是看待问题的成熟方式。 “他在学术上很年轻，但也比同龄人年轻很多，”Yampolsky 说。 “和这么年轻、这么聪明的人一起工作很有趣。他有这种智力成熟，更像是同龄人。”

Braverman 通过思考基本机制开始了他对分形的研究：在计算方面，是什么让 Julia 集特别？大部分工作是由美国数学家约翰米尔诺建立的，他现在在石溪大学工作。 Braverman 在 Cook 的指导下并与 Yampolsky 合作，研究了 Milnor 的策略，并开始专注于计算异常困难的集合，例如需要多次迭代才能揭示它们是保持接近还是逃逸到无穷大的复杂函数。与库克一起，布雷弗曼调查了以前的模型，这些模型提供了什么时候可以计算以及什么时候不能计算的规则。随着时间的推移，研究人员开始怀疑：某些函数是否会如此复杂以至于根本无法计算它们的 Julia 集？

这就是计算机科学的观点被证明是无价的地方。那种问题——有没有我们不能解决的问题，我们能证明吗？ ——是典型的理论计算机科学。在动力系统中，一个由数值模拟驱动的领域，它近乎异端。

“直觉是它们可能很难计算，但都是可行的，”Yampolsky 说。 “也许你只需要等待很长时间才能看到这张照片，但没有任何实际障碍。”

Braverman 和 Yampolsky 联系了 Milnor，后者对动态系统的计算机科学方法感到兴奋，并提供了反馈。多年来，该小组一直在戳戳这个奇怪的问题，寻找方法来证明无法找到某些 Julia 集——这本来就很难证明。但在 2005 年，受到一个法国小组的发现的启发，Braverman 和 Yampolsky 找到了前进的道路，打破了研究人员的直觉。他们发现对于某些函数，Julia 集不仅难以计算，而且被证明是不可能的。

“这是数学奇迹之一，”Yampolsky 说。 “还有一点震惊。”动力系统社区最初反对这个想法。 “但有时数学思想有时间，你知道吗？”

他们的第一篇论文为可计算的 Julia 集制定了明确的规则，并提出了一种算法来查找无法计算集的函数。这一发现导致了大量的结果。 Yampolsky 说，最令人震惊的事情之一是证明他们找到不可计算的 Julia 集的方法实际上是唯一的方法。这项研究首先为 Braverman 的硕士论文奠定了基础，然后为他在多伦多的博士工作奠定了基础。他与 Cook 的论文描述了用于研究 Julia 集的计算模型，最终他和 Yampolsky 撰写了一本关于该主题的书，于 2009 年出版

布雷弗曼说，当他开始这项工作时，“这是一个有点过时的领域”，但这并没有打扰他。他说：“在计算机科学领域，有这个想法的金发姑娘区域。” “如果太容易了，结果就会泛滥成灾。如果太难，它就会变得如此稀少，以至于人们失去兴趣，你就无法维持一个社区。”

数学乐观主义

在读研究生期间，布雷弗曼建立了另一个重要的联系——这次是与一位名叫安娜的研究生同学、未来的心理学家和他未来的妻子。她也出生在俄罗斯，巧合的是，在海法的同一所小学里，她比布雷弗曼落后一年。 “我们实际上从来没有说过超过一个字，”布拉弗曼说。但两个家庭最终都搬到了加拿大，马克和安娜再次相遇——这一次有更多的话——并于 2007 年结婚。

获得博士学位后，布雷弗曼花了更多时间旅行和建立联系。他首先在普林斯顿的高级研究所呆了一个月，在那里他遇到了理论计算机科学家 Anup Rao，他将与他一起稳定工作多年。之后，他在马萨诸塞州剑桥市的微软新英格兰研究院担任了两年的博士后研究员。在微软之后，布雷弗曼回到加拿大，在多伦多大学任教一年。

在寻找金发姑娘问题的过程中，他参与了各种项目，从医疗保健数据挖掘到未解决的关于随机性的数学问题。普林斯顿大学的数学家 Naor 说，Braverman 喜欢直接陷入棘手的问题。 “假设你面前有一块巨石，很长一段时间以来，人们一直试图绕过这块巨石，”Naor 说。然后有人出现并制定了解决它的计划。如果它不起作用，这个人会找到另一个计划，然后是另一个。 Naor 认为，这种精神表现出一种根深蒂固的乐观主义。 “如果你不乐观，你就永远无法绕过那块巨石，”他说。 “马克有。”

他于 2011 年加入普林斯顿大学。安娜以临床心理学家的身份加入该大学，这对夫妇在距离计算机科学大楼三个街区的地方买了一栋房子。在这一点上，他的家比其他任何地方都要久。他们将继续生两个孩子——一个在 2016 年，另一个在 2018 年。

定居新泽西后，Braverman 开始从事信息复杂性领域的工作，这是 Rao 在 2008 年将他介绍给他的领域。信息复杂性从更大的信息论学科中衍生出来，始于 1948 年 Claude Shannon 的开创性工作制定了一个人通过渠道向另一个人发送信息的数学框架。那篇论文试图量化信息，并向世界介绍了“比特”的概念，作为其基本的、保守的单位。香农写道，根本的挑战是以精确或接近精确的精度将数据从一个点传递到另一个点。如果数据包含一些“简单”的东西，比如随机数字流，并且通道是无噪音的，那就很容易了。

但是，如果这些数据具有复杂的统计关系（例如英语中的数十万个单词）或通道嘈杂，那么任务很快就会变得棘手。借用统计力学的工具，香农将数据压缩的概念形式化，并将“熵”的概念改编为与消息中信息量相关的量。布雷弗曼说，他的关键见解是将信息本身的熵与通道的容量——信息发送的速率——区分开来。在这些条件下，只要消息的熵不超过通信信道的容量，就可以执行通信任务。这个想法自然地提出了另一个问题：通过通道发送消息所需的最少熵是多少？

耶路撒冷希伯来大学的理论计算机科学家Omri Weinstein说：“香农表明，如果对话是单向的，只有一方发言，那么你可以优化压缩数据，”这意味着尽可能少的熵和布雷弗曼在普林斯顿的第一批博士生之一。

香农正在考虑嘈杂的电话线。布雷弗曼专注于将香农的工作扩展到单向传输之外。特别是，他不仅想考虑如何发送数据，还想考虑如何共享和操纵数据，例如通过算法。他可以看到香农的想法可以应用于通信复杂性领域的方式，它问：计算的通信成本是多少？这个问题更贴切地反映了互联网上每天发生数十亿次的情况：两方，例如买方和卖方，相互通信以完成某些交易。他们只关心结果——知道付了多少钱，付给谁——而不是他们如何到达那里。实现该目标可能需要反复来回传递信息。布雷弗曼看到信息论的形式主义可以适应这种情况，但它会很复杂。这种交流的基础是什么数学？起初，这个挑战提出了一系列离散的、可接近的问题，与香农最初探索的单向情况不同。

“最初我的动机是解决一些问题，但我更喜欢建立理论，所以结果证明有一个理论要建立，”布雷弗曼说。建立理论意味着解决问题、设计证明、寻找与其他领域的联系以及招募研究生来提供帮助。 “在接下来的 10 年里，我花了很大一部分时间来研究它。”

寻找答案

Braverman 最大的贡献是建立了一个广泛的框架，该框架阐明了描述交互式通信边界的大而通用的规则——这些规则为通过算法在线发送数据时提出压缩和保护数据的新策略提出了新的策略。

以前的研究人员研究了两个人如何来回发送信息，特别是在一个人可能什么都不知道或者他们没有重叠信息的简单情况下。在 1970 年代，计算机科学家研究并解决了如果两个人一开始就有一些重叠信息会发生什么情况。但 Braverman 和他的合作者首先证明这些交换是计算任务，而不是数据传输任务。

例如：想象两个人每个人都有一个动物列表和一个协议，这是一种来回发送消息的方式。他们想确定他们有哪些共同的动物，如果有的话，以及要弄清楚这一点需要付出多少努力。在这种情况下，每个人都有一些信息开始（他们知道他们在谈论动物），并且每条消息都会添加到该信息中。信息的增加与以比特为单位的通信成本有关， Braverman 和 Rao 在 2011 年的一篇论文使这种联系比以往任何时候都更加紧密。

这一证明使他们对沟通产生了其他见解，包括一个称为直和问题的问题版本。它涉及成本问题：解决一个问题的多个副本是否与解决一次并乘以重复次数具有相同的通信成本？还是有“批量折扣”？在数据传输的情况下，直接和成立。但 Braverman 和 Rao表明，对于交互式情况，该问题相当于一个看似无关的问题，称为“交互式压缩”问题。这问如果两个人交换一百万条短信但只学习 1,000 位信息，是否可以将交换压缩为 1,000 位守恒？使用 Braverman 和 Rao 的工作，研究人员已经证明答案是否定的。

信息论和计算复杂性之间的这种联系也促使 Braverman 在两个或更多人之间共享数据压缩时寻找新的方法来优化数据压缩——这是在线交流的核心。在 2011 年至 2020 年期间，Braverman 和他的合作者描述了压缩两方或多方之间共享信息的数学规则。这项工作引发了其他问题；例如，他还与他的合作者和学生一起研究了对话类型如何推动沟通成本。

布雷弗曼不仅破解了这些问题。他引入了一种新的视角，允许研究人员首先将它们表达出来，然后将它们翻译成数学的正式语言。 Braverman 的理论为探索这些问题和确定可能出现在未来技术中的新通信协议奠定了基础。

“这是一个非常强大的理论，”1994 年获得内万林纳奖的高等研究院理论计算机科学家Avi Wigderson 说， “这是香农工作的美丽、丰富和复杂的延伸。”

尽管布雷弗曼在他以前的学生和博士后推动该理论的过程中继续指导该理论，但他的大部分工作已经完成。现在他的兴趣更多地集中在一个称为机制设计的新领域，该领域使用经济学和博弈论的数学方法。他最近还与 Naor 在构建称为 Lipschitz 函数扩展的东西的长期挑战方面取得了进展，这是经典分析和几何中的一个问题。

“他确实带来了计算机科学的见解，这与我长大的方式非常不同，”Naor 说。 “他的观点与我的想法不同。但这也是一种直觉和观点。他有一种他已经发展起来的哲学，一种他带来的观点。”

赢得算盘奖章不会改变这一切。如果有的话，布雷弗曼对数学的广泛好奇心多年来加深了，这支持了他毕生的论点：解决棘手的问题实际上就是找到合适的语言来研究它们。在其他学科中并非如此：你不能只是偶然发现 Alpha Centauri，或意外发现 Covid-19 疫苗。巨大的进步通常需要技术和多年的增量进步。但在数学和计算机科学中，大解决方案可能就在附近，隐藏在一种未破译的语言中。

“你基本上会觉得自己一无所知，但在解决问题的五分钟内完成，”他说。这就是他想传授给他的学生和数学继承人的东西。他说，像算盘这样的大奖“是一种责任。它使你成为大使。这让学生们明白，这些并不是完全疯狂的想法。”