CAREER: Information Theoretic Methods in Communication and Computational Complexity

点击翻译按钮获取中文摘要

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.