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

点击翻译按钮获取中文摘要

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.