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.