CAREER: Common Links in Algorithms and Complexity

算法设计领域构建了能够快速解决感兴趣的计算问题的聪明程序。复杂性理论领域在数学上证明了“下界”，表明没有这样聪明的程序存在于（其他）核心问题。从直觉上看，这两个领域的工作似乎是截然相反的。该项目的主要目标是发现算法设计和复杂性理论之间反直觉的新联系，并研究由这些联系建立的桥梁的科学后果。一个理论框架的潜在影响——社会的、科学的和其他方面的——很难被高估，它将导致对计算机能做什么和不能做什么的细粒度理解。这个项目的重点是通过研究算法和下界之间看似相反的任务之间的联系，探索实现更好理解的具体步骤。该项目的另一个目标是使复杂性研究更接近现实世界的计算，并向从业者介绍将影响他们工作的复杂性方面。最终目标是教育推广，通过致力于学习计算机科学的在线论坛，教授暑期学校课程，以及与媒体合作向公众传播理论计算机科学（包括算法和下限之间的联系）。PI寻求算法和复杂性之间的共同联系：反直觉的相似性和桥梁，将导致更深入地了解这两个领域。计算机科学中的一个核心问题是著名的P对NP开放问题，它是关于允许短解的组合问题的难度。这样的问题总是可以通过？蛮力?，尝试所有可能的解决方案。蛮力总能被更聪明的搜索方法所取代吗？这个问题很重要；目前还没有令人满意的答案，具体的答案似乎还很遥远。传统的观点认为，一般来说，蛮力是无法完全避免的，但在数学上，大多数自然搜索问题都可以非常迅速地解决，而不需要任何蛮力。计算下界是我们这个时代最伟大的科学奥秘之一：关于它们有许多猜测和信念，但具体的结果却很少。此外，该理论还受到？复杂性障碍?这表明大多数已知的证明方法都不能证明强下界。PI的长期目标是帮助发现和发展新的思维方式，这将揭开下限的神秘面纱，并阐明计算可能性的极限。PI假设从算法的角度来看下限是关键：例如，PI的早期工作表明，电路可满足性问题的算法（略优于蛮力搜索）暗示了电路复杂性的下限。在过去的几年中，PI已经开发了几个新的链接，并提出了更多需要研究的链接。在这个项目探索的各个角度中，潜在的科学应用是巨大的，从逻辑电路设计到网络算法，到改进的硬件和软件测试，到更好的最近邻搜索（在计算机视觉，DNA测序和机器学习中有自己的应用），以及密码学和安全性。

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.