NSF-BSF: AF: Small: Lower bounds on concrete complexity

计算复杂性理论是对可以使用有限的计算资源（如处理能力，内存和通信）进行计算的研究。目标是研究有效计算的数学可能性和限制。现代生活继续通过使用可以访问有限资源的计算设备（如手机）而改变。了解这些设备可以计算什么是非常宝贵的。复杂性理论的结果提供了一个指南，以帮助使用这些设备实现有效的解决方案。在这个项目中，我们调查有关沟通的基本问题，被视为一种稀缺资源。例如，如果问题A的最佳解决方案需要沟通X，而问题B的最佳解决方案需要沟通Y，那么同时解决这两个问题所需的沟通是什么？答案不一定是X+Y。研究人员将建立数学工具来解决这类问题。为了实现这些目标，他们将使用各种数学学科的思想，如几何，分析和组合学。该项目将侧重于与通信复杂性有关的几个基本问题。研究人员将研究与理解压缩交互式通信协议的限制，证明某些算法的运行时间的下限以及证明对数秩猜想有关的问题。这包括一种方法来证明严格的下界著名的不相交性问题的通信复杂性。在布尔电路领域，重点是证明有界系数的算术电路的下界和理解使用阈值门的布尔电路。关于多面体的可拓复杂性，该项目的重点是证明多面体近似的新下界，以及探索可拓复杂性和电路下界之间的新联系。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computational complexity theory is the study of computation that can be carried out using limited computational resources like processing power, memory and communication. The goal is to investigate the mathematical possibilities and limits of efficient computation. Modern life continues to be transformed by the use of computational devices that have access to limited resources, like cell phones. It is invaluable to understand what can be computed by such devices. Results in complexity theory provide a guide to help implement efficient solutions using such devices. In this project, we investigate fundamental questions about communication, viewed as a scarce resource. For example, if the best solution to problem A requires communication X, and the best solution to problem B requires communication Y, what is the communication required to solve both problems at the same time? It turns out that the answer need not be X+Y. The investigators will build mathematical tools to address this kind of question. In order to pursue these goals, they will use ideas from various mathematical disciplines like geometry, analysis and combinatorics. The project will focus on several fundamental questions related to communication complexity. The investigators will study questions related to understanding the limits of compressing interactive communication protocols, proving lower bounds on the running times of certain kinds of algorithms, and proving the log-rank conjecture. This includes an approach to proving tight lower bounds for the famous disjointness problem in communication complexity. In the realm of boolean circuits, the focus is on proving lower bounds for arithmetic circuits with bounded coefficients and understanding boolean circuits that use threshhold gates. With regards to the extension complexity of polytopes, the project focuses on proving new lower bounds on approximations of polytopes, as well as exploring a new connection between extension complexity and circuit lower bounds.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.