CAREER: Common Links in Algorithms and Complexity

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

• 批准号: 1552651
• 负责人: Ryan Williams
• 金额: $ 55万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-12-15 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552651&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测序等方面都有自己的应用）和机器学习），以及密码学和安全性。