CAREER: Common Links in Algorithms and Complexity

职业：算法和复杂性的常见联系

• 批准号: 1741615
• 负责人: Ryan Williams
• 金额: $ 50.33万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-01-20 至 2021-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1741615&HistoricalAwards=false
• 关键词: CAREER; Common; Links; Algorithms; Complexity

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.

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