CAREER: Limits of Communication
CAREER: Limits of Communication
批准号:
1149018
负责人:
Alexander Sherstov
金额:
$50.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2012
资助国家:
美国
项目状态:
已结题
起止时间:
2012-06-01 至 2018-05-31
中文摘要
考虑一个函数,它的参数分布在多个各方,使得任何一方都不可能单独计算它。通信复杂性理论研究需要多少位通信来评估功能。通信复杂性是由安德鲁·姚在三十多年前开创的,现已成为理论计算机科学的一个中心研究领域。首先,把交际作为一种有限的资源来学习具有很强的实践动机。此外,许多其他计算模型中的公开问题归结为关于通信的问题。到目前为止,通信复杂性理论已经影响到理论计算机科学中的几乎所有学科,从经典的图灵机和电路模型到最近的诸如数据结构、学习理论和量子计算等主题。该奖项旨在研究通信复杂性理论中三个长期悬而未决的问题:(I)多方通信的限制;(Ii)存在量词和通用量词交替使用的通信的限制;(Iii)通信的组合和矩阵理论观点的猜想等价性。这些问题的解决将在理论计算机科学中产生超出通信的重大后果,包括ACC电路和神经网络的下界,DNF公式的有效学习,以及量子通信和经典通信的等价性。提出的问题的进展将利用机器学习和矩阵理论等其他学科的见解,并为其贡献新的想法。该奖项提供了不同难度水平的研究问题的充分来源,并将用于指导学生和教授新的研究生和本科课程。作为该奖项不可或缺的一部分,国际和平协会将促进洛杉矶地区的理论研究,并积极参与科学传播。
英文摘要
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.
期刊论文(2)
专著(0)
科研奖励(0)
会议论文
DOI:
10.1007/s00037-021-00211-4
发表时间:
2019-02
期刊:
computational complexity
影响因子:
1.4
作者:
[Alexander A. Sherstov]
通讯作者:
Alexander A. Sherstov
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
AC0 阈值度和符号秩的近最优下界
DOI:
10.1145/3313276.3316408
发表时间:
2019
期刊:
51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子:
--
作者:
[Sherstov, Alexander A., Wu, Pei]
通讯作者:
Wu, Pei
AF: Small: Polynomials, Communication, and Query Complexity
-
批准号:2220232
-
项目类别:Standard Grant
-
资助金额:$60.0万
-
财政年份:2022
-
负责人:Alexander Sherstov
-
依托单位:
AF: Small: Multiparty Communication, Polynomials, and Noise
-
批准号:1814947
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2018
-
负责人:Alexander Sherstov
-
依托单位:
海外基金