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）

Quantum communication complexity of distribution testing

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

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

The Approximate Degree of DNF and CNF Formulas

DNF和CNF公式的近似度