AF: Medium: Theory of Computation - New Algorithmic and Hardness Techniques

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

The goal of this project is developing new theoretical tools for understanding the power and limits of efficient computation. Underlying every computer application, (and indeed computer industry, from networks to security to optimization to storage and so on) available today are ingenious algorithms that utilize the various important resources (time, space, communication) in an efficient manner. However, for not-yet-existing applications (or industries), is their unavailability due to the lack of efficient algorithms that may yet be discovered, or are the underlying problems really intractable, and thus impossible to solve efficiently? This project seeks both new efficient algorithms, as well as new methods for proving intractability. The ideas to be explored by the project use tools and connections to problems from several areas in mathematics, physics and information theory, and promise progress on some of the deepest problems in computational complexity.On the algorithmic side, the project will focus on a wide variety of optimization problems in which the search space has some symmetry. The project will explore algebraic and geometric techniques to analyze both alternating-minimization and geodesic algorithms to solve new problems for which efficient solutions do not yet exist: these include classes of non-convex problems and exponentially large linear programs. On the intractability side, this research will focus on extending a new method of "lifting" hardness results for complex computational models, such as Boolean circuits, proof systems, communication networks and semi-definite programming, from hardness results for much simpler models such as decision trees and polynomials.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.