CAREER: Information Theoretic Methods in Communication and Computational Complexity

从计算机科学的早期开始，计算问题的难度就有很大的不同，从容易到中等困难，从难以解决到完全无法解决，这一点很清楚。计算复杂性理论是计算机科学的一个分支，它试图严格地和数学地研究计算问题的内在难度，以解决问题所需的特定资源的数量来衡量，并根据问题的内在难度将问题组织成类。相关资源的例子包括处理时间、存储空间和计算机间通信。通信复杂性涉及到后一种资源，并询问必须在不同计算机之间通信多少位才能解决输入在这些计算机之间分配的问题。人们对通信复杂性有着很大的内在兴趣，因为与之相关的互联网驱动的应用程序种类繁多。此外，在过去的15年里，通信复杂性已经成为一个领域，它将许多看似不同的理论计算机科学领域结合在一起，其中一些领域并不直接涉及通信；例如电路复杂性、查询复杂性、量子计算、算法博弈论、优化和分布式计算。近年来，信息论已被证明是研究传播复杂性的有力工具，因此在传播影响的复杂性理论的其他各个领域也是如此。我已经在最近的工作中探索了这个主题，并且是最近一篇论文的作者之一，该论文正式引入了信息复杂性的概念，并描述了它与通信复杂性的关系。我随后的另一项工作应用信息论技术证明了关于通信复杂性的定理，并反过来应用这些定理来探索与通信无关的问题的内在困难。本项目的主要目标是从两个方面继续这一工作。首先，我将继续开发和扩展我所称的信息复杂性框架，并尝试将其应用于尚未成功应用的计算模型。第一个目标的一个值得注意的子目标是使用这个框架来理解量子计算的局限性。其次，我将寻求研究与复杂性理论的其他领域有联系的通信复杂性中的某些具体问题。我们关注的两个具体领域是(1)数据流计算的复杂性和(2)电路的复杂性，重点是浅电路的功率。

From the very early years of computer science it has been clear thatcomputational problems vary greatly in difficulty, ranging from easy tomoderately hard to intractably hard to outright unsolvable. Computational complexity theory is the branch of computer science thatseeks to rigorously and mathematically study the inherent difficulty ofcomputational problems, measured as the amount of a certain resource (orresources) required for their solution, and organize problems intoclasses based on their inherent difficulty. Examples of relevantresources include processing time, storage space and inter-computercommunication. Communication complexity involves the latterresource and asks how many bits must be communicated between differentcomputers to solve a problem whose input is split between thesecomputers. There is plenty of intrinsic interest in communication complexity,because of the large variety of Internet-driven applications where it isrelevant. In addition, over the last decade and a half, communicationcomplexity has been emerging as an area that unites many seeminglydisparate areas of theoretical computer science some of which do notdirectly involve communication; examples are circuit complexity, querycomplexity, quantum computing, algorithmic game theory, optimization anddistributed computing. In recent years, information theory has proved itself to be a powerfultool in the study of communication complexity, and therefore in thevarious other areas of complexity theory that communication impacts. Ihave already explored this theme in my recent work and was an author ofa recent paper that formally introduced the concept of informationcomplexity and described its relation to communication complexity.Other subsequent work of mine has applied information theoretictechniques to prove theorems about communication complexity and appliedthese theorems in turn to explore the inherent difficulty of problemsnot directly involving communication.The main goal of this project is to continue this line of work in twoways. First, I shall continue to develop and extend what I call theinformation complexity framework and attempt to apply it to models ofcomputation where it hasn't yet been applied successfully. A noteworthysubgoal of the first goal will be to use this framework to understandthe limitations of quantum computation. Second, I shall seek to studycertain concrete problems in communication complexity that have knownconnections to other areas of complexity theory. Two specific areas Ishall focus on are (1) the complexity of data stream computations and(2) circuit complexity, with an emphasis on the power of shallowcircuits.