CAREER: Limits of Communication

职业：沟通的限制

基本信息

批准号：
1149018
负责人：
Alexander Sherstov
金额：
$ 50万
依托单位：
University of California-Los Angeles
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2012
资助国家：
美国
起止时间：
2012-06-01 至 2018-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1149018&HistoricalAwards=false
关键词：
CAREER Limits Communication

项目摘要

Consider a function whose arguments are distributed among several parties, making it impossible for any one party to compute it in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate the function. Pioneered by Andrew Yao over thirty years ago, communication complexity has become a central research area in theoretical computer science. First of all, studying communication as a limited resource has a strong practical motivation. Moreover, open problems in many other computational models reduce to questions about communication. To date, communication complexity theory has impacted almost every subject in theoretical computer science, from classical models such as Turing machines and circuits to more recent topics such as data structures, learning theory, and quantum computing.This award takes aim at studying three longstanding open questions in communication complexity theory: (i) the limits of multiparty communication; (ii) the limits of communication with alternating existential and universal quantifiers; (iii) the conjectured equivalence of the combinatorial and matrix-theoretic views of communication. A resolution of these questions would have major consequences in theoretical computer science beyond communication, including lower bounds for ACC circuits and neural networks, efficient learning of DNF formulas, and an equivalence of quantum and classical communication. Progress on the proposed problems will exploit insights from, and contribute new ideas to, other disciplines such as machine learning and matrix theory. This award provides an ample source of research problems at various levels of difficulty and will be used in advising students and teaching new graduate and undergraduate courses. As an integral part of the award, the PI will promote theory research in the Los Angeles area and take an active part in scientific dissemination.

考虑一个函数，其参数分布在多方之间，使得任何一方都不可能单独计算它。通信复杂性理论研究需要多少通信比特来评估功能。由安德鲁·姚（Andrew Yao）在三十多年前开创的通信复杂性已成为理论计算机科学的中心研究领域。首先，研究传播学作为一种有限的资源，具有很强的实践动机。此外，许多其他计算模型中的开放问题归结为有关通信的问题。迄今为止，通信复杂性理论几乎影响了理论计算机科学的每个学科，从图灵机和电路等经典模型到数据结构、学习理论和量子计算等最新主题。该奖项旨在研究三个长期存在的开放通信复杂性理论中的问题：（i）多方通信的局限性； (ii) 交替使用存在量词和全称量词的沟通限制； (iii) 组合和矩阵理论的传播观点的猜想等价性。这些问题的解决将对通信以外的理论计算机科学产生重大影响，包括 ACC 电路和神经网络的下限、DNF 公式的有效学习以及量子和经典通信的等价性。所提出问题的进展将利用机器学习和矩阵理论等其他学科的见解，并为其贡献新的想法。该奖项提供了各种难度级别的研究问题的充足来源，并将用于为学生提供建议以及教授新的研究生和本科生课程。作为该奖项的有机组成部分，PI将推动洛杉矶地区的理论研究并积极参与科学传播。