AF: Small: Lower Bounds for Computational Models, and Relations to Other Topics in Computational Complexity

计算复杂性理论是一个数学领域，研究计算机的极限和执行计算任务所需的资源。在我们的信息时代，计算的数学理论是至关重要的，计算机几乎涉及到我们生活的每一个部分。计算复杂性对于设计高效的通信协议、安全的密码协议以及理解人类和机器学习也是至关重要的。研究计算模型的极限是理论计算机科学中最令人兴奋、最具挑战性和最重要的课题之一，对于理解计算的能力和发展计算理论是必不可少的。该项目将研究不同计算模型所需资源的下界，以及计算复杂性的相关主题。该项目将集中在三个主要研究方向：学习的时空下界：在最近的一系列工作中，Pi和他的合著者证明了一些最广泛研究的学习问题需要超线性内存大小或超多项式数量的样本。该项目将进一步研究记忆/样本学习的下限以及它们与复杂性理论中其他主题的关系。记忆限制下的学习下限表明了记忆在学习和认知过程中的重要性。它们可能与理解人类学习相关，并可能对机器学习、人工智能和优化产生影响。算术电路的下界：该项目将研究算术电路和公式的下界，以及算术电路和公式的子类。由于多项式在理论计算机科学中的中心性，算术电路的下界可能会在理论计算机科学中产生更广泛的影响。通信复杂性的下界：在最近的一系列工作中，PI和他的合著者证明了信息复杂性和通信复杂性之间的第一个差距。这些结果表明，交互通信协议对其信息内容的压缩是不可能的，从而表明交互类似于香农信源编码定理和霍夫曼编码是不可能的。通信复杂性和信息复杂性的分离结果可能与电气工程相关，特别是与高效通信协议的设计有关。该项目将进一步研究这些主题，更广泛地说，通信复杂性的下限及其与计算复杂性中其他主题的关系。

Computational complexity theory is a mathematical field that studies the limits of computers and the resources needed to perform computational tasks. A mathematical theory of computation is crucial in our information age, where computers are involved in essentially every part of our life. Computational complexity is also essential in designing efficient communication protocols, secure cryptographic protocols and in understanding human and machine learning. Studying the limits of computational models is among the most exciting, most challenging, and most important topics in theoretical computer science and is essential for understanding the power of computation and for the development of a theory of computation.The project will study lower bounds for the resources required by different computational models, as well as related topics in computational complexity. The project will focus on three main research directions:Time-Space lower bounds for learning: In a sequence of recent works, the PI and his coauthors proved that some of the most extensively studied learning problems require either a super-linear memory size or a super-polynomial number of samples. The project will further study memory/samples lower bounds for learning and their relations to other topics in complexity theory. Lower bounds for learning under memory constraints demonstrate the importance of memory in learning and cognitive processes. They may be relevant to understanding human learning and may have impact on machine learning, artificial intelligence and optimization. They also have applications in cryptography.Lower bounds for arithmetic circuits: The project will study lower bounds for arithmetic circuits and formulas, as well as for subclasses of arithmetic circuits and formulas. Lower bounds for arithmetic circuits may have a broader impact within theoretical computer science, because of the centrality of polynomials in theoretical computer science.Lower bounds for communication complexity: In a sequence of recent works, the PI and his coauthors proved the first gaps between information complexity and communication complexity. These results show that compression of interactive communication protocols to their information content is not possible, and hence show that interactive analogs to Shannon's source coding theorem and Huffman coding are not possible. Separation results of communication complexity and information complexity may be relevant to electrical engineering and in particular to the design of efficient communication protocols. The project will further study these topics, and more generally, lower bounds for communication complexity and their relations to other topics in computational complexity.