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

AF: Small: Multiparty Communication, Polynomials, and Noise

AF：小：多方通信、多项式和噪声

基本信息

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

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814947&HistoricalAwards=false
关键词：
AF Small Multiparty Communication Polynomials

项目摘要

Communication complexity theory studies the minimum amount of communication, measured in bits, required in order to compute functions whose arguments are distributed among several parties. In addition to the basic importance of studying communication as a bottleneck resource, the theory has found a vast number of applications in many areas, including machine learning, mechanism design, streaming algorithms, data structures, pseudo-random generators, and VLSI layouts. This project tackles fundamental questions whose resolution will have a significant impact on the discipline. This work will exploit insights from, and contribute new ideas to, other areas such as quantum computing, computational learning, and approximation theory. The project is an ample source of research problems at various levels of difficulty and will be used in advising graduate and undergraduate students. The investigator will integrate this research into his graduate and undergraduate teaching, take an active part in scientific dissemination, and promote theoretical computer science in Southern California.This project comprises two related components. First, the investigator will tackle longstanding open problems in the study of multiparty communication, such as settling the communication requirements of the set disjointness problem and breaking the logarithmic barrier for multiparty communication lower bounds. The second, complementary component of this project will advance the study of analytic representations of Boolean functions. Here, the investigator aims to obtain tight lower bounds for the polynomial approximation and sign-representation of the k-element distinctness function, constant-depth circuits, and Boolean formulas of arbitrary depth. The two research components of this project are intimately related in that they require the same class of analytic techniques. Indeed, major advances in communication complexity over the past two decades have been obtained by transforming, explicitly or implicitly, communication protocols into multivariate polynomials of comparable complexity and by analyzing the resulting approximation questions. The planned research on multiparty communication and polynomials is further unified by a focus on noise, in the sense of imperfect output or adversarial corruption of intermediate computations.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.

通信复杂性理论研究的是计算参数分布在多方的函数所需的最小通信量（以比特为单位）。除了研究通信作为瓶颈资源的基本重要性之外，该理论在许多领域都有大量的应用，包括机器学习，机制设计，流式算法，数据结构，伪随机发生器和VLSI布局。该项目解决的基本问题，其解决方案将对学科产生重大影响。这项工作将利用来自其他领域的见解，并为其他领域提供新的想法，如量子计算，计算学习和近似理论。该项目是一个丰富的研究问题的来源，在不同程度的困难，并将用于指导研究生和本科生。研究者将把这项研究融入到他的研究生和本科生教学中，积极参与科学传播，并在南加州推广理论计算机科学。首先，研究者将解决多方通信研究中长期存在的开放问题，例如解决集合不相交问题的通信要求和打破多方通信下限的对数障碍。第二，该项目的补充组成部分将推进布尔函数的解析表示的研究。在这里，调查人员的目的是获得严格的下限的多项式近似和符号表示的k元素的独特功能，恒定深度的电路，和布尔公式的任意深度。这个项目的两个研究部分是密切相关的，因为它们需要相同的分析技术。事实上，在过去的二十年中，通信复杂性的主要进展已经通过显式或隐式地将通信协议转换为具有可比复杂性的多变量多项式并通过分析所产生的近似问题而获得。计划中的多方通信和多项式的研究通过对噪声的关注而进一步统一，即不完美的输出或中间计算的对抗性腐败。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
影响因子：
0
作者：
Sherstov, Alexander A.;Wu, Pei
通讯作者：
Wu, Pei

The approximate degree of DNF and CNF formulas

DOI：
10.1145/3519935.3520000
发表时间：
2022-06
期刊：
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Alexander A. Sherstov
通讯作者：
Alexander A. Sherstov

Quantum Communication Complexity of Distribution Testing

量子通信分布式测试的复杂性

DOI：
10.26421/qic21.15-16-1
发表时间：
2021
期刊：
Quantum Information and Computation
影响因子：
1
作者：
Aleksandrs Belovs; Arturo Castellanos; Francois Le Gall; Guillaume Malod;Alexander A. Sherstov
通讯作者：
Alexander A. Sherstov

Vanishing-Error Approximate Degree and QMA Complexity

消失误差近似度和 QMA 复杂度