CAREER: Information Theoretic Methods in Communication and Computational Complexity

职业：通信和计算复杂性中的信息论方法

• 批准号: 0448277
• 负责人: Amit Chakrabarti
• 金额: --
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2011-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0448277&HistoricalAwards=false
• 关键词: CAREER; Information; Theoretic; Methods; Communication

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.

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