CAREER: Structural Communication Complexity

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

The field of communication complexity is about situations where twoparties, call them Alice and Bob, each hold a separate piece of data,and they wish to collaboratively solve some computational problem thatdepends on both their inputs. How much will they need to communicateback-and-forth to achieve their goal? The field encompasses both upperbounds---i.e., the design of protocols that allow Alice and Bob tosucceed using only a small amount of communication---as well as lowerbounds---which show that no such efficient protocol exists for certainproblems (i.e., Alice and Bob will need to communicate many bits tosucceed). This serves as a natural model of distributed computing,motivated by big data and cloud computing concerns. More generally, itcan be used to model any situation where flow of information betweendifferent components of a system forms a bottleneck; for this reason,communication complexity has applications to many other areas ofcomputer science. This project will develop deep technical tools to makeprogress on several longstanding problems and central issues incommunication complexity and its various application areas. The unifyingtheme of this project is the importation of insights and techniques fromstructural complexity, which is the area of theoretical computer sciencedevoted to classifying problems according to their inherentcomputational difficulty. The education component will address thechallenges of facilitating flow of ideas between theory andapplications, and transitioning students from coding to problem solvingto research.One specific type of tool relevant to this project is "liftingtheorems", which relate communication complexity to the simpler model ofquery complexity. The investigator will continue to develop and applysuch lifting theorems to address structural questions in communicationcomplexity and beyond. This project will: develop fundamentally newlower bound techniques for powerful communication models, strengthen andunify classic and widely-used results, clarify the delicate relationshipbetween communication and the amount of information Alice and Bob revealabout their inputs, advance the understanding of computational problemsconcerning communication complexity itself, and use structural insightsto deepen the connections with circuit complexity, proof complexity, anddata structures.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.