CAREER: Common Links in Algorithms and Complexity

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The field of algorithm design builds clever programs that can quickly solve computational problems of interest. The field of complexity theory mathematically proves "lower bounds," showing that no such clever program exists for (other) core problems. Intuitively, it appears that these two fields work on polar-opposite tasks. The major goal of this project is to discover counter-intuitive new connections between algorithm design and complexity theory, and to study the scientific consequences of the bridges built by 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. This project is focused on exploring concrete steps towards a better understanding, via studying links between the seemingly opposite tasks of algorithms and lower bounds. 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, teaching summer school courses, and collaboration with the media on communicating theoretical computer science (including links between algorithms and lower bounds) to the public. The PI seeks common links between algorithms and complexity: counter-intuitive similarities and bridges which will lead to greater insight into both areas. 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. Computational lower bounds are among the great scientific mysteries of our time: there are many conjectures and beliefs about them, but concrete results are few. Moreover, the theory is hampered by ?complexity barriers? which show that most known proof methods are incapable of proving strong lower bounds. The PI's long-term objective is to help discover and develop new ways of thinking that will demystify lower bounds, and elucidate the limits of possibilities of computing. The PI hypothesizes that an algorithmic perspective on lower bounds is the key: for example, earlier work of the PI shows that algorithms for the circuit satisfiability problem (which slightly beat brute force search) imply circuit complexity lower bounds. The PI has developed several new links within the past few years, and has proposed many more to be investigated. Among the various angles explored in this project, 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.