权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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）的组合和矩阵理论的观点通信的expectured等价。这些问题的解决将对理论计算机科学产生重大影响，而不仅仅是通信，包括ACC电路和神经网络的下限，DNF公式的有效学习，以及量子和经典通信的等价性。在提出的问题上的进展将利用来自其他学科的见解，并为其他学科（如机器学习和矩阵理论）提供新的想法。该奖项提供了一个丰富的研究问题的来源，在不同程度的困难，并将用于指导学生和教学新的研究生和本科生课程。作为该奖项的组成部分，PI将促进洛杉矶地区的理论研究并积极参与科学传播。