AF: Small: Lower Bounds in Complexity Theory Via Algorithms

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Computers have transformed nearly every aspect of life, by automating and assisting in helping people work more efficiently. But while researchers know much about what computers can do, there is still comparatively little known about what computers cannot do. This phenomenon is the problem of proving "complexity lower bounds". Lower bounds are among the great scientific mysteries of our time: there are many mathematical conjectures and beliefs about lower bounds---indeed, the security of the Internet and cryptography relies on such conjectures being true---but concrete results are few. The major goal of this project is to leverage humanity's vast knowledge of computer algorithms to prove new lower bounds: put another way, the goal is to use the power of computers to prove limitations on them. A secondary goal is to study the scientific consequences of these connections. It is hard to overestimate the potential impact---societal, scientific, and otherwise---of a theoretical framework which would lead to a fine-grained understanding of what computers can and cannot do. Another goal of the project is to bring complexity research closer to real-world computing, and to introduce practitioners to aspects of complexity that will impact their work. A final goal is educational outreach, through online forums dedicated to learning computer science and collaboration with the media on communicating theoretical computer science to the public. To give one example of a lower bound, a central question in computer science is the famous P versus NP open problem, which is about the difficulty of combinatorial problems which admit short solutions. Such problems can always be solved via brute force, trying all possible solutions. Can brute force always be replaced with a cleverer search method? This question is a major one; no satisfactory answers are known, and concrete answers seem far away. The conventional wisdom is that in general, brute force cannot be entirely avoided, but it is still mathematically possible that most natural search problems can be solved extremely rapidly, without any brute force. The mathematical theory is hampered by negative results showing that most known proof methods are incapable of proving strong lower bounds. A primary objective of this project is to help discover and develop new ways of thinking that will demystify lower bounds, and elucidate the limits and possibilities of computing. The major hypothesis of this project is that an algorithmic perspective on lower bounds is the key: for example, an earlier project led by the same research team shows that algorithms for the circuit-satisfiability problem (which slightly beat brute force search) imply circuit-complexity lower bounds. Other algorithmic problems, such as estimating the acceptance probability of a circuit without using randomness, and finding "bad" inputs which prove that a piece of code does not correctly compute a function, also turn out to be useful for proving lower bounds. The potential scientific applications are vast, ranging from logical circuit design, to network algorithms, to improved hardware and software testing, to better nearest-neighbor search (with its own applications in computer vision, DNA sequencing, and machine learning), and to cryptography and security. 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.