AF: Small: Computational Complexity Lower Bounds: Time, Space and Communication

虽然计算机已经彻底改变了我们的世界，但执行计算任务所需的资源却鲜为人知。发展计算的数学理论在我们这个信息时代是至关重要的，在这个时代，计算机几乎涉及到我们生活的方方面面。计算复杂性是对执行计算任务所需资源数量的研究，对于理解计算的能力和发展计算理论至关重要。它在设计有效的通信协议和安全的加密协议以及理解人类和机器学习方面也是必不可少的。证明不同计算模型和不同计算任务所需资源的下限，是理论计算机科学中最令人兴奋、最具挑战性和最重要的主题之一。该项目将研究计算复杂性的下界，重点研究两个方向：与学习相关的下界；并且，研究量子和经典计算模型的相对能力。更详细地说，我们将重点关注以下方向。(1)学习的记忆-样本下限：在线学习算法的记忆/样本下限是一个非常令人兴奋的研究方向，在最近的一系列工作中得到了研究。例如，证明了任何学习奇偶的算法要么需要二次大小的内存，要么需要指数数量的样本。该项目将进一步研究学习的记忆/样本下限及其与计算复杂性中其他主题的关系。(2)量子和经典计算模型的相对能力：该项目将研究各种模型中量子和经典复杂性之间的差距。特别是，它将研究量子和经典通信复杂性之间的分离，以及量子和经典算法在学习记忆/样本权衡的背景下的相对能力。(3)与学习相关的电路复杂度下限：机器学习，特别是深度学习的惊人成功，激发了对密切相关的计算模型的研究。该项目将研究线性阈值电路和其他与学习相关的电路模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

While computers have revolutionized our world, the resourcesrequired to perform computational tasks are poorly understood.Developing a mathematical theory of computation is crucial in ourinformation age, where computers are involved in essentially everypart of our life. Computational complexity, the study of the amountof resources needed to perform computational tasks, is essentialfor understanding the power of computation and for the developmentof a theory of computation. It is also essential in designingefficient communication protocols and secure cryptographic protocols,and in understanding human and machine learning. Proving lowerbounds for the resources required by different computationalmodels, and for different computational tasks, is among the mostexciting, most challenging and most important topics in theoreticalcomputer science. The project will study computational complexitylower bounds, focusing on two research directions: Lower boundsrelated to learning; and, studying the relative power of quantumand classical computational models.In more details, we will focus on the following directions. (1)Memory-Samples lower bounds for learning: memory/samples lowerbounds for online learning algorithms is a very exciting researchdirection that has been studied in a line of recent work. Forexample, it was proved that any algorithm for learning paritiesrequires either a memory of quadratic size or an exponential numberof samples. The project will further study memory/samples lowerbounds for learning and their relations to other topics incomputational complexity. (2) The relative power of quantum andclassical computational models: The project will study gaps betweenquantum and classical complexity in various models. In particular, itwill investigate separations between quantum and classical communication complexity,as well as the relative power of quantum and classical algorithmsin the context of memory/samples trade-offs for learning. (3)Circuit complexity lower bounds related to learning: The amazingsuccess of machine learning, and in particular deep learning,motivates a study of closely related computational models. Theproject will study linear-threshold circuits and other models ofcircuits that are related to learning.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.