计算机科学助理教授Joshua布罗迪解释了如何计算适合文科
听:约书亚·布罗迪在计算是一个文科
在这个演讲,计算机科学助理教授约书亚·布罗迪讨论了计算的理论研究。布罗迪使计算的参数,计算思维和理论属于文科课程。
“在我们的研究领域,理论计算,我们要分类继承困难的问题。所以对于一个给定的问题,有多少资源是必要的和足够的,”他说。“你给我任何计算问题,我想知道所需的最少的资源解决问题,我想知道为什么你不能做得更好。”
增加计算能力使伟大的科学的进步,从映射人类基因组启用安全的电子商务。同时,计算见解揭示学科包括经济学、生物学、化学问题。
布罗迪的主要研究领域是理论计算机科学和通信复杂度特别感兴趣。
音频记录:
丰富:嘿,每一个人。所以,我Wicentowski丰富。我在这里的计算机科学系。这是我的荣幸今天向大家介绍约书亚布罗迪。约书亚从达特茅斯学院在2010年获得博士学位,并两个博士后。一个在北京圣克劳迪亚大学,然后在丹麦。他在2013年加入我们。约书亚教上层课程和算法和可能的团体方法,和教许多艺术课程的入门序列。他还教他指示读数在许多研究领域上的正常的教学工作量。
丰富:约书亚已经在学院领导地位和计算机科学系,特别是最近,他领导一个团队的学生在国际大学生程序设计竞赛。刚刚过去的这个周末,他们来到了世界总决赛将于3月底在葡萄牙。所以,希望约书亚去葡萄牙。
丰富:今天,约书亚将是和你谈论他的研究,在该地区的通信复杂度的下界和其他相关领域的计算机科学。约书亚数篇论文,他与学生,今天他会告诉你为什么计算是一个文科。所以,请和我一起欢迎约书亚。
约书亚:谢谢。谢谢你富有的介绍。是的,我要谈谈我的一般研究领域,理论计算机科学,希望把它放在文科课程良好的上下文。在我开始演讲之前,我想给一些确认。尤其是我想谢谢尤金·朗的教员奖学金提供我第二学期的支持。我有很多美好的事情在我去年的年假。我发表了两个不同的文件。我与埃里克Blais滑铁卢大学合作生产一个将于明年出版的手稿,我超级兴奋,我想更加让人觉得振奋。有大量的时间去充实和补充我研究管道。所以,休眠的很多小项目,我终于有足够的时间思考更多,和准备他们希望学生研究项目。
约书亚:当我去教师讲座与没有孩子的人,他们总是谈论确认,他们必须去度假,他们有一只狗,他们做了很好的东西。我设法[听不清00:02:43]我们的第二个孩子。这是我们所做的个人。我不会说他醒来每20或30分钟。他只是尖叫起来,原来打每20或30分钟9月到11月。我无法想象这是什么一直在想如果我当时实际上是教学。
约书亚:所以,我只是想过去很快在高层次上我的研究项目是什么。我的博士论文是在通信复杂性,我将告诉你在这说话。最近,我一直非常感兴趣的应用通信复杂性到其他领域,有很多通信复杂性之间的连接在不同的领域和计算机科学。所以,即使我没有做通信复杂性,这是一种好的迈出第一步进入其他研究领域,尤其是研究与学生。所以,我会试着年底谈论更多的话题。
约书亚:那么,这个演讲将大致划分为四个不同的部分。所以,首先,我想给你一个动力,特别是如果你是说,人文学科教授,和/或你从未CS21在你的生活。我希望说服你为什么学习计算是一个值得追求的目标。我将给你一个概述什么是沟通的复杂性,和几个例子如何使用通信复杂性有直觉到计算机科学的其他领域。然后,我很快就会打一些其他的研究项目,我做了自从我来到斯沃斯莫尔。最佳线上娱乐
约书亚:好的。我想从这第一张幻灯片,我有你所有文件。你必须选择一个。所以,你愿意用两个非常大的数字,或者你愿意添加两个非常大的数字?
观众:添加。
约书亚:如果我们做遥控器的问题,这将是一个优秀的教师课堂习题。是的,所以几乎每个人都说添加,我们不会进入一个正式的证明为什么,但是你可能有很好的直觉的感觉,即使你没有CS21,为什么你想添加。乘法比较难,它需要更多的工作。这个金块,这个直觉,而且比较难,在高级别上,事情是这样的我想谈谈整个谈话。如果你想要一个速写为什么还比较难,还需要更多的工作。除了,你只是做一种线性扫描旁边的数字和添加一个数字。乘法,您了解了在小学里,你必须把每个数字与其他数字。作为一名计算机科学家,这需要N的平方操作。这个使用n个操作,这个不太容易。
约书亚:顺便问一下,会有一些技术方面的细节在这说话。我要打破惯例与一般观众会谈和一点点进入低水平技术细节。但我想序言这说,几乎每一个低水平的技术细节,你真的不需要理解它。我想让你做的是有一个高水平的印象。也许你会认为我的理解,也许你会相信有很好的理由这样做的原因。一点点的符号是不可避免的,所以我提供这个方便的活动挂图在左边。大魔神的符号是一个向上的绑定如果我们使用这么多计算或更少。所以如果我们想解决方案,希望在大O数量尽可能小。
约书亚:好的,所以通常我们并不讨论操作的数量需要两个不同的问题。在理论计算机科学,我们更有可能把一个计算问题,并比较不同解决方案的计算问题。所以,你可以想想乘法和问自己如果N的平方是最好的,我们能做的,答案是否定的。这是因为计算机科学。这N的平方操作,我最初会认为这是[听不清00:06:57]时代,但他们实际有糟糕的节奏。这是公元630年(伯曼Gupta 00:07:04)发明的。原因是因为[听不清00:07:08]罗马人没有零,所以他们不能做这个操作。
约书亚:工业计算机发明后不久,第二次世界大战。在50年代,他们的公司开始广泛使用。计算机科学的许多方面的问题,我们有了新的解决方案,新的有效的解决方案在50年代和60年代。因此,[Karasuba 00:07:30]做乘法,1.585 N的,…,这是一种非理性的指数,但没关系。只有不到两个,更有效率。所以很快,一旦我们有电脑和动机做更好的乘法算法,我们得到了运行时下降很快。我登录,再从N,除以2,继续这样做,直到你得到一个。多少次你除以两个登录吗?远小于n[听不清00:07:59]的日志,日志的日志……
约书亚:好吧,这大O符号是所有计算机科学家使用。捕获的东西,这是一个很好的方法,因为我们关心如何计算水平尺度与输入的大小。一面是,无视一个常数因子。恒定的因素,在这里工作,和可能的原因之一,乘法算法没有发明电脑发明之前是因为出于实用的目的,对于小数字或小的长度,这些新算法没有更有效的在现实世界中。他们只进入大计算数字越来越大。但在计算机科学中是很常见的,我们有工具,我们只是等待应用程序。
约书亚:在80年代早期,这确实发生了。所以,密码学的世界在一段时间的革命性也许三年在80年代初,在一个非常高的水平,现代密码学是基于使用数学非常大的数字加密效率,同时,如果有人试图把你的消息和解密它,他们不应该,他们必须解决一个计算困难的问题,还是一个问题,我们希望是困难的。乘法叫做因式分解的逆操作,我们不知道如何做是有效的。这个应用程序内的密码仍然是计算机科学领域。我认为这是一个很好的理论计算洞察不同的区域。
现代密码学约书亚:这整个想法,哦,顺便说一下,如果您曾经使用过亚马逊网上购买东西,你使用现代密码学,基于这一概念,有些事情很容易计算,和其他人是很难的。(听不清00:09:54)乘法可能四、五千岁的开放问题。这是仍在研究。所以,艺术是在2007年完成。不要问什么是锁着。内部日益增长的函数,只是非常非常缓慢。所以,不到5。所以我们说它小于宇宙中粒子数。这种狂热实际上是本地的,他是一个教授Ken状态。所以,我只是觉得这很酷,你可以提出新的见解和一个更好的算法,五千年来,人们一直在研究的东西。
约书亚:所以,接下来我要做的是谈论,我进入细节之前,我的研究领域,一些计算机科学以外的其他领域或计算观点起到了一定作用。他们扮演了一个角色。很多生物或物理过程可以被建模的计算。我要给一个例子从经济学和心理学而不是一个例子。所以,第一个例子我想做的事,这是一个名为Curby西蒙的计算机科学家。他在1975年获得图灵奖,就像计算机科学诺贝尔奖。他还研究过心理学和经济学,他是唯一有图灵奖和诺贝尔奖的人。他的经济学研究,他获得了诺贝尔奖的部分是基于这个想法有界00:11:20合理性。
约书亚:他的研究之前,显然在经济学中,模型通常被人类和人类组织。每个人都认为他们最优的可能他的洞察力,这并不总是发生。有时候,人们只是做的东西不够好。这是经济研究,但这绝对是一个计算的观点。为什么人们不能做的事情完全最优,这是因为找出最优解是非常困难的,需要大量的工作。所有这些直觉你有加法比乘法,这是同样的直觉。提出最优解是困难的。我们知道很多优化问题在计算机科学中,但我们不知道实际上任何有效的方法。所以计算机科学智慧,这是明确的,但它是Curby西蒙连接行为分析我猜。
约书亚:从心理学的例子,我想把离家更近一点。所以,巴里·施瓦茨曾经是这里的心理学教授。他做了这个研究选择的矛盾。如果你是他的同事,请告诉我,如果我在这里说一些完全错误的。这里的想法是,有更多的选择可以减少幸福,所以他做了一些经验,你有一个大范围的笔,你需要选择一个你最喜欢的带回家。事实证明,人不满意他们如果他们得到了更多的钢笔。对我来说,这个计算的洞察力…这一观点也计算在一个非常相似的方式寻找工作。需要一点点的工作来决定哪一个你最喜欢的,如果你有更多的选择,比这更多的工作。
约书亚:从计算机科学的角度看,我会祈祷很感兴趣了解这个尺度的函数n .所以你有不同的通信,抱歉,我们理解不同的计算过程。因此找出哪一个是最好的,其实是比较全对吗?我们知道他们业余时间成本。也许你正在做良好的排序算法和登录,或者你只需要做一个扫描,和图哪一个是最好的。计算机科学家知道这三件事的计算复杂度。
约书亚:好的,我想回到我的实际研究。我假设你以前没有研究通信复杂性,除非你是紫色,但是我要给你一个高水平的概述,几个例子,然后我们将讨论它的应用。就一般而言,非常广泛,我们的研究领域,理论计算,我们要分类继承困难的问题。所以对于一个给定的问题,有多少资源是必要的和充分的。我认为这是一个研究问题,这是最让我着迷。你给我任何的计算问题,我想知道所需的最少的资源解决问题,我想知道为什么你不能做得更好。
约书亚:这两个问题,资源是必要的和充分的,最终被不同的子字段(CS 00:14:49理论)。算法设计是充分的资源。所以,如果您只想显示这些许多资源是足够的,你设计一个解决这个问题的算法。你分析它,拍拍自己的背,继续你的一天。另一面,有多少资源是必要的,传统上被认为是更加困难,因为你不能拿出一个解决方案。你需要表明,不管你做什么,无论你如何试图解决这个问题,你至少需要这些资源。所以,我认为这是一个硬币的两面。的其余部分将讨论第二个。有一个很好的理由。因为这是我的竞争优势在哪里。 So, if your students here eventually do research, you will start to have lots of interests. You may or may not progress in every single area. It just so happens that lower bounds are where I get the results.
约书亚:好的,那么我做过的研究通常是下界。理想情况下,我想买数字工具捕获下界在很多不同的领域。沟通的复杂性让我这么做,我们将讨论如何去做。下界我真正关心的最重要的是现在的信息在现实世界的计算过程,尤其是在我们有大量的数据,超过我们能够处理,我们如何处理。理想情况下,我想工作与其他研究人员关心下界,并展示如何证明下界的问题。
约书亚:这是一般的通信复杂性模型。再一次,不关注技术细节,保持在高水平,各种各样的问题。我们有两个不同的人。他们都有输入和计算一个函数的两人的输入。他们的目标是用最有效的方式,我们的目标是学习通信复杂性和理解多少通信需要解决这些问题。所以,我将举几个例子。第一个是平等,两名球员都是爱丽丝和鲍勃。它几乎总是Alice和Bob,这就是我们的约定。所以,我们可以在这里有爱丽丝和鲍勃。他们每个人都有嵌入流。 Again, they could each have numbers, and they want to see if they're equal.
约书亚:计算机科学家喜欢比特,所以只是在默认情况下,输入比特流,我们想做它用最少的沟通。作为基准,一个容易的事情,他们可以做,爱丽丝可以送她整个输入Bob。他们需要沟通的一部分原因是他们每个人都只有一半的输入。没有沟通,他们不知道足够的计算这个函数。爱丽丝,但我们会将她的整个输入发送给鲍勃,鲍勃现在有X和Y,看着它们,看到它们相等,然后发送回一点说他们是否相等。
约书亚:事实证明,这是你能做的最好的。所以,任何形式的通信协议计算平等已发送大量涌入。我不打算详细证明,但是你可以问我离线。问题是,只要他们确定的。所以,如果他们没有随机性的来源。但是,如果他们允许选择消息发送基于某种概率分布或某种随机性,然后他们可以做这个有百分之一使用八个比特错误。这是为数不多的沟通问题,这实际上会用所有的时间。一个花园各种这是也许你有Netflix账户,你想下载电影,这些都是一般大,巨大的文件。你想知道这个大,巨大的文件被损坏,因为它被下载。所以他们可能做的是一些短而平等测试最后相信你得到的是实际上它应该是什么。
约书亚:另外一个例子,(听不清00:19:17),现在我要换东西。我希望你会在这里,但是没关系。所以,教务长Willie-LeBreton最近成为教务长。突然,她很忙。丰富的和她想要建立一个会议,他们只能设置一个会议时都有空闲时间。教务长Willie-LeBreton很忙,她知道丰富素有交谈很多。所以,他们不想把他们的整个日历开槽的学期和交换。理想情况下,他们会这样做的方式是非常有效沟通。因此,他们不仅把整个学期讨论寻找一个空槽。
约书亚:那么,他们只是想把一些沟通。微不足道的一件事,他们能做的是,富人可以谈了很多,把他整个自由安排。教务长Willie-LeBreton找到时间表,可以找到一个免费的位置,和进度会议。原来这就是最好的,他们可以做的事情。他们不能做任何更好,即使他们已经随机化。这个特定的问题(听不清00:20:37)被称为女王通信复杂性。现在这可能看起来超级简单,最后论文从2004年实际上给一个直观地理解为什么你需要尽可能多的通讯有插槽。
约书亚:事实证明,你需要说一点关于周三9,一下周三外,每一个可能的空闲时段。丰富的教务长Willie-LeBreton可能需要交换一些信息来确定是否这是一个特定的空闲时段。然而,这是25年的密集研究之前,我们有一个完整的理解。也叫女王沟通的复杂性,因为它使用的所有。
约书亚:好的。我想进入这些沟通如何降低轮得到使用。这些看起来像两个例子,平等和[听不清00:21:34],则不是。他们是非常有用的为这些应用程序。每一个这些应用程序,应用程序,我的意思是如何使用通信复杂性表明,其他地区也难。每一个这些应用程序将在完全相同的方式工作。如果你已经阻断了一点,因为一些技术细节,现在是时候停止间距为。这也许是最重要的幻灯片演讲。
约书亚:每一个这些降低轮,每一个这些硬度结果将在完全相同的方式发生。三个步骤:我们要证明沟通问题的下界,我们要显示也许你最喜欢的问题不合理有效的解决方案,构建一个协议的通信问题,第三步需要这两个步骤在一起,得出结论,你不能有一个合理的解决你的问题。再一次,因为它是非常重要的,我将更直接拼出来。
约书亚:第一步,你证明一个下界的沟通问题。第二步,你展示如何构建一个解决方案来交流……你最喜欢的问题……对不起,绊倒我的文字里。第二步,您正在构建一个解决沟通问题的使用您的特定问题的一些解决方案。第三步帕克这些不平等在一起。这就是我们要证明下界每一次。一个巨大的胜利,即使你不在乎通信复杂性,是通信复杂性现在在你的领域。所以,我们知道很多现有的沟通问题,我们有一个深入了解他们的计算复杂度。
约书亚:通常,我们可以免费把第一步,把现有的沟通从架子上下界,刚插进去就可以了。从历史上看,第二步相对容易做到。第一步是非常困难的。所以,你得到一个重大胜利通过回收利用现有的通信问题。好吧,我将向您展示几个例子。所有这些不管是好是坏都是在大的计算机科学工程领域。但是,我首先是尽可能远离我的研究领域。最初的原因研究通信实际上是一种集成电路设计复杂性。所以,这里的意思是有人在工程部门正在设计一个集成电路。这是一个芯片,计算一个特定的函数。 The things that they care about when they building these chips is area and time. So, we want these chips to be as fast as possible because the customers want speed.
约书亚:我们也希望这些芯片工厂尽可能小,因为它的成本钱每一次他们打印一个芯片。所以越小,成本越低,越少时间计算函数,客户越快乐。所以事实证明,很多功能,你可能想要设计一个芯片,正确权衡最终被无论面积乘以时间的平方,这是你如何建立一个通信协议的其中一个集成电路设计。你会想象,你有一个芯片的功能,本质上,你要给有芯片爱丽丝和鲍勃芯片。
约书亚:所以,你可以想象这个芯片的存在。你要用它来解决任何沟通问题Alice和Bob要做的,和他们会模仿这个芯片的运行计算这个函数来解决他们的实际问题。所以,有很多不同的功能,我们有同样的下界。它的面积乘以时间下界的平方。从制造商的角度是谁让这些芯片,我们现在知道正确的权衡,这意味着,如果我想要快一点,我需要支付的地区。反之,如果我想使它更便宜的让这些芯片和减少区域,然后时间炸毁。它炸毁多少钱?如果我减少面积,它实际上的平方根,不是那么糟糕。如果我试图让它更小的时间,然后我需要支付二次处罚空间。
约书亚:那么,这些芯片制造商关心这两个不同的资源,他们会以同样的方式转移到沟通。几个其他领域我们知道通信下界,数据结构。我看到你们中的许多人已经CS35,祝贺你,这是正确的选择。所以,一个通用的数据结构问题。我们有很多我们想要存储的数据。也许我们不需要太多空间来存储。我们想查询这些数据和回答关于数据的存储问题。我们的想法是如果我们可以有更多的空间,我们也许能够减少查询时间。如果我们能够花一点额外的工作我们所做的每一次查询,我们可以做它在有限的空间里更简洁。
约书亚:那么,这又是也是沟通的复杂性。我们要人格化在完全相同的方式随着超大规模集成电路。从本质上讲,这种通信复杂性问题是将模型一个CPU和内存之间的对话。这将捕捉大量的数据结构的性能问题。第三个是相关的。流算法,这些流算法背后的想法是,你有更多的数据,可以在您的机器上。所以,想象乔尔试图监视的所有互联网流量的网络流量的斯沃斯莫尔。最佳线上娱乐我们想运行统计数据,来确定我们的网络受到了攻击。基于各种统计数据,我们跑,我们不仅可以知道如果有人试图攻击斯沃斯莫尔网络,但很多时候我们可以告诉攻击他们想做什么。最佳线上娱乐
约书亚:这是数据太大的问题,适合您的机器。
所以,两个品种的下界,任何希望计算的统计数据,你需要随机化或近似。没有这两个,你实际上需要保存你所有的互联网流量是无望的。但是当你都,会发生很多有趣的事情。同样的技术工作。我们要把网络流量在两个。爱丽丝会效仿第一一半的交通流算法,该算法在内存的内容发送给鲍勃,谁来完成仿真例程。
约书亚:这个想法是随机化和近似,都是必要的。这看似深奥,或者这只是有趣的人关心下界。这巨大的实际意义的公司做这些类型的算法。所以,这是一个花园的经验法则,它几乎总是如此,你需要随机性。它几乎总是如此,你需要近似。公司正在试图做流算法的特定问题几乎从来没有想去做它没有随机性和近似。所以,这些下界实际上改变了这些算法越来越发达。是非常有益的正确答案是什么。好吧。
约书亚:我免费应用程序。有很多和很多很多的应用程序。我想谈论一个因为我co-invented技术。所以,这是财产相关的测试。属性测试算法是另一件事,我们试着处理大量的数据。在这种算法中,我们有更多的数据比我们甚至可以看。所以,我们想在我们的数据计算某些函数甚至没有花时间去做一个完整的扫描。所以有时候,你可能会想做快速扫描,希望看看你的输入有一个特定的属性,并继续你的一天。在这些示例中,输入你要有一些功能。你要看看这个函数有一个属性,而不需要计算每一个值的函数。
约书亚:那么,查理的要做一些计算。总的来说,这是一个很绝望的任务。找出它是否有一个属性,你几乎总是需要计算一切。所以,这个分区属性测试一种放松。很多时候,我们不需要告诉如果F总是属性。我们只需要告诉F是否有财产和的财产。对于很多计算机科学应用程序,输入,你得到的是吵闹的。所以,试图区分是否有属性和远离拥有财产。如果你想在一个非常高的层面,我们给自己一些空间,希望这个空间是足够的,我们可以做一个速写超级有效。
约书亚:所以我想给一个具体的例子,你可能关心的功能属性。这个函数…这个属性被称为K迟到,所以这个F是K迟到如果X或一些比特,K的碎片。这个X或函数,如果你还没有见过它,我要把K的N位、数的数量,如果是奇数,我要说的是一个值,输出是一个,否则我会说输出是零。这个研究在sub-linear时间算法社区老下界的平方根来之前。新的下界等于K。
约书亚:我看到在这一点上,有相当数量的空白的楼梯。祝贺你,你是在正确的点在这说话。你应该真正关心这个特殊的财产或sub-linear时间算法?也许不是,但我会告诉你,sub-linear时间属性的算法是一个非常活跃的分支,它测试,和这个研究团体关心下界的人很多,所以他们的研究,甚至一半的研究,是在证明下界计算是必要的。所以,即使你不关心它,做这项工作的人做的,结果在2012年我们的工作之前,他们使用一个非常,本质上是一个非常古老的技术,证明他们的下界。所以,我们要利用新技术。你介意把我的电话…
演讲者4:做什么?
约书亚:无所谓。我的手机响了。我要让它响。没关系。
约书亚:那么,我们要读这从一个特殊的味道这剥离问题,我已经谈过了。输入说。输入说听不清00:33:16子集,在这种特殊情况下,我们会向你保证,只是非常小的子集。所以,你应该把这个K /两个小n .结果相比,如果我们限制输入小集,我们可以节省通信,但是我们仍然得到一个下界的ωK .所以,我要建立一个通信协议为K剥离这个属性的测试算法,和我的角度,我又要做在完全相同的方式,我们用真正的幻灯片电路和数据结构,等等。
约书亚:这是我们的计划。我有两套不同。他们要做的第一件事就是,他们将集和创建不同的功能。所以,爱丽丝在这里有三位。她函数X是两位,5和9,X或在一起。鲍勃会做同样的事情,然后他们会创建一个函数,H,就是这些函数的X或。这个函数H是一个K或一堆位,和其它一些碎片。现在我们要运行一个属性测试算法对H K模仿这个问题的部分原因是Alice和Bob实际上并不知道什么是H。爱丽丝看到F, G鲍勃看到,没有人看到。所以,他们每次都要沟通要计算H (X)对于一些输入。
约书亚:那么,他们将运行这个属性测试人员每次他们需要计算H (X), H (Y, Y z .他们会交换F (X)和G (X,他们会来来回回,模仿房地产测试仪,并最终如果属性测试输出,他们会输出什么测试仪输出。事情就是这样,爱丽丝和鲍比在两个大使馆支付。如果这些大使馆不重叠,那么X或者在一起的时候,这是一个X或K不同的大使馆。K / 2, K / 2。但是,如果他们相交,他们都有相同的一点,这些位彼此抵消。如果他们相交,那么它实际上不是一个K戏仿函数。相信我,这是非常远离K模仿。
约书亚:那么,这个协议的成本,他们需要为每次交换两位想计算H (x)的数量如果计算查询的数量乘以2,是这个通信协议的成本。我们知道这个通信协议必须使用至少ωK资源。K资源是必要的。如果你两边除以两个,现在我们说大约K资源解决K模仿是必要的。我冲走大量艰苦的细节在地毯下,证明这对K降低剥离,涉及解决剥离是超级困难。但是我们需要这么做,我们只是从架子上拿了这个下界。
约书亚:所以,一旦我们有这个功能,我的作者埃里克•Blais是一个属性测试人,所以他知道很多属性测试功能。不关注这张幻灯片的技术细节。这是我们能想到的所有功能。我们采用相同的技术,我们有很多新的下界。所以,一切都在红色比我们之前已经知道的。在黑人实际上并不大,尤其是在艺术水平的背景下,我认为有一个巨大的价值,因为我们比之前被证明更简单。特别地,这两个界限,K模仿开方到K,这很好。
约书亚:如果你看看这些证据,基本上是五页的密集的数学,和我是一个大风扇的数学作为下一个人,但这些证明你从一行到下一个,您可以验证这一基于前一行的下一行是真的。所以,你穿过整个五页,最后,你可能会说,是的。这个结果是正确的,但我们没有深入了解为什么这些结果是正确的。不仅是沟通下界可以获得良好的新下界,如果你购买,我们有一个深刻的理解这些通信下界,然后他们提供很多见解,不是到很多资源,但为什么。
约书亚:好的。所以,我要快速喝的水,然后谈论一些最近的研究项目。我认为通信复杂性是可怕的。这是一个非常深,美丽的数学领域。如果你不关心,这就是你在乎的。这是一种良性的反馈循环。我们所知道的更多的通信复杂性问题,深入了解,就越容易在其他领域得到应用。我们对下界的更多的应用程序,更好的激励我们证明沟通下界。这张幻灯片的内容吓了我当我还是个研究生开始。有很多细节和细微差别。
约书亚:通过演讲的最后,我想谈谈为什么这是一个好地方本科研究和为什么它不是人们应该吓一跳。好吧。所有这些工具在左上角,我们如何证明沟通下界,这将是在范围在这说话,但它本质上是一个很多数学。所以,很多不同的领域,人们已经知道的数学好,他们已经能够使用它来证明通信算法。所以,因为很少数量的这些沟通问题出现的地方,我认为有很多价值的理解这些很少沟通尽可能深入的问题。这个工作我做了一些合作者基本上可以描述为比你以往任何时候都更想知道平等问题。这是一个非常细粒度的理解如果你关心Alice和Bob之间的互动。假阳性,假阴性率,紧下界五或六个不同的参数。
约书亚:这个十字路口sub-disjointness非常相关的问题,而不是说他们是不相交的,是否我们要实际输出的十字路口。原来的密码社区,这是正确的问题。这[听不清00:40:19]问题实际上是一个直接的结果在世界这个属性测试我的研究。所以,事实证明这些下界了一点。上个月K下界出来,但事实证明K剥离实际上并不是正确的看问题。有一个相关的问题叫做汉明00:40:43距离。
约书亚:那么,埃里克和我,和他的研究生(听不清00:40:47),给定时汉明距离的下界,并建立这个连接属性测试,但这只是特殊情况的汉明距离是一个或三个。我们有很好的理由来处理特殊情况。你要相信我。本文使用完全不同的技术,超级有趣。所以我做了我的研究被称为强烈的直和。一种直和的问题,也许你想计算一个函数不是一次,但是很多不同的时间,你要知道,如果你想计算K次,会导致因子K炸毁的沟通。或者,你可以在很多不同的摊销成本。
约书亚:我总是教经典的例子是,你只是一个大屋子的土豆皮。这是非常枯燥的工作。大概没有人真正知道如何削土豆皮。但是,如果你有1000,你会好转。所以,直和的结果可能不持有土豆脱皮的问题。根据谷歌搜索,这幅图片是教授的分级作业。所以,如果你是一个学生,你总是想问教授是什么感觉当他们评分,特别是如果他们有一个大的也许20或30的学生…很抱歉。如果你想知道我们的感觉当我们分级大量的家庭作业,这就是我们的感觉。不… this is a really [inaudible 00:42:29] for professors. Is grading 25 copies of the same exam going to cost you 25 times the time? Hopefully not. Hopefully you will find that students make the same mistakes over and over, and maybe you can kind of cut down the missed time.
约书亚:但在不同的计算模型,有时直和的结果,有时没有。我们的结果显示随机查询的复杂性,计算K的副本实际上导致了比K炸毁,我认为这是超级奇怪的和有趣的。所以,我会给你一个快速的素描。直觉是,如果你计算F K不同的输入与整体错误X 1,你可以做的一件事就是单独计算每个副本,但较低的错误。X / K,所以整体X是一个错误。我们想要做的是证明你有来计算每个复制误差较低。
约书亚:因此,我们要采取一个协议,或一个算法计算K复制,修复所有的输入和把我们一份我们需要计算输入,和果酱在K的调查在不同的副本。我们想证明我们可以做到这一点的方式计算这只复制一次,你必须用超低的错误。这个日志K炸毁来自较低的错误。所以我们不能这样做,但是我们可以展示的是F低误差的算法。但有时,算法只是警察中止。这中断概率是超高,或许终止概率三分之一。但是,我们展示功能,仍然很难即使你流产的一些时间。
约书亚:这是我所做的在我休假的研究。其他问题的研究中,这是一种non-communication复杂性的东西我已经到因为他们相关领域。我有一篇论文我和马里奥·桑切斯非常兴奋。这种多党跳点难的问题是一个经典的候选人。我们不知道通信复杂性,但我们认为很难,有不错的结果。在通讯方面,我们说,我们发现这超级难沟通问题只是一个比以前更方便。所以,我们稍微改善了上限,但我们证明在底层的技术,这些随机图,有很多东西你可以说通过随机图。我们有一个新的转折,允许[听不清00:45:18]。
约书亚:我做的工作与乔[听不清00:45:19]。这成为了乔的荣誉论文。对于很多数据结构,你可能想做所有的内存访问提前提前,尤其是当你有一个系统的多核心,或记忆的远方。轮的CPU和内存之间的交互可以是昂贵的。我们表明,这个经典问题称为前任搜索,有一个巨大的代价un-adaptively。我认为只是因为时间我要跳过最后一个工作,项目。
约书亚:整个夏天的一般研究项目。最少的资源,什么是最少的资源必然是足以解决问题吗?我认为这是自然法则。他们的基础科学。至少我希望我给你体验告诉你,这些东西可以学习严格,严格,他们值得研究。我深信在核心通信问题。其中有一个非常小的数量用于下界的到处都是。所以,我想学习他们尽可能。,我想说的只是一些事情从剩下的时间在学生研究。所以,我有很多成功的出版与大二学生和研究生博士后的时候开始,我认为这幅画风景的沟通的复杂性和细微差别实际上是一个优势,而非劣势,与本科生工作。
约书亚:我认为的原因之一…只要我有大局的人理解,学生真的不需要知道每一个细微差别。所以,我可以给他们一个开放问题在一个特定的皱纹这些沟通问题,和一个特定的变体。什么丰富的时间,像夏天的研究项目,你不需要的全球视角的研究空间。这完全是如果学生认为,教授,这是一个有趣的问题,值得研究。学生你可能不知道……你可能概念化的研究作为我要做地球抖动,新的突破研究。很多更低的水平,和有很多的问题,我们知道在一个高水平的与这个特定的通信问题。为一个特定的味道,但也许我们没有完全理解。
约书亚:如果教授很好地努力发展这些问题,循序渐进是完全好,我认为有一个巨大的空间不同的循序渐进,访问本科生,但与此同时,合法的研究(Lavart 00:48:23)社区外的人就会发现有价值的和有用的。所以,我认为这需要为教授工作。所以,在高级别上,我的目标是保持专业知识和看到大局。我认为这需要一点努力,为大学生工作选择很好的研究问题。但是,在我的知识之间的差异有一个优势和学生的知识。我需要更多的知识来理解什么是大局,为什么这些问题是很有趣的。但是希望学生可以把一个特定的,具体的研究问题,知道你在做什么特别的问题不知道整个空间。
约书亚:所以,我认为这是一个好地方停止。谢谢。
