AF: Large: Collaborative Research: Exploiting Duality between Algorithms and Complexity

AF：大：协作研究：利用算法和复杂性之间的二元性

• 批准号: 1212372
• 负责人: Ryan Williams
• 金额: $ 45万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1212372&HistoricalAwards=false
• 关键词: AF; Large; Collaborative; Research; Exploiting

Meta-algorithms are algorithms that take other algorithms as input. Meta-algorithms are important in a variety of applications, from minimizing circuits in VLSI to verifying hardware and software to machine learning. Lower bound proofs show that computational problems are difficult in the sense of requiring a prohibitive amount of time, memory, or other resource to solve. This is particularly important in the context of cryptography, where it is vital to ensure that no feasible adversary can break a code. Surprisingly, recent research by the PIs and others shows that designing meta-algorithms is, in a formal sense, equivalent to proving lower bounds. In other words, one can prove a negative (the non-existence of a small circuit to solve a problem) by a positive (devising a new meta-algorithm). This was the key to a breakthrough by PI Williams, proving lower bounds on constant depth circuits with modular arithmetic gates. The proposed research will utilize this connection both to design new meta-algorithms and to prove new lower bounds. A primary focus will be on meta-algorithms for deciding if a given algorithm is 'trivial' or not, such as algorithms for the Boolean satisfiability problem. The proposed research will devise new algorithms that improve over exhaustive search for many variants of satisfiability. On the other hand, it will also explore complexity-theoretic limitations on how much improvement is possible, using reductions and lower bounds for restricted models. Satisfiability will provide a starting point for a more general understanding of the exact complexities of other NP-complete problems such as the traveling salesman problem and k-colorability. The proposal addresses both worst-case performance and the use of fast algorithms as heuristics for solving this problem. This exploration will be mainly mathematical. However, when new algorithms and heuristics are developed, they will be implemented and the resulting software made widely available. This research will be incorporated in courses taught by the PI's, at both graduate and undergraduate levels. Both graduate and undergraduate students will perform research as part of the project.

元算法是将其他算法作为输入的算法。在各种应用中，从最小化VLSI的电路到验证硬件和软件到机器学习，元算法在各种应用中都很重要。下限证明表明，在需要大量的时间，内存或其他资源来解决的意义上，计算问题很困难。这在密码学的背景下尤其重要，在密码学的背景下，确保没有可行的对手可以打破代码至关重要。令人惊讶的是，PIS和其他人的最新研究表明，从形式意义上讲，设计元算法等同于证明下限。换句话说，可以通过正（设计新的元算法）来证明一个负面（小电路的不存在以解决问题）。这是Pi Williams突破的关键，在具有模块化算术大门的恒定深度电路上证明了下限。拟议的研究将利用这种联系来设计新的元算法并证明新的下限。主要的重点将放在元算法上，以确定给定算法是否“琐碎”，例如布尔可满足性问题的算法。拟议的研究将设计新的算法，以改善对许多令人满意的变体的详尽搜索。另一方面，它还将使用限制模型的减少和下限来探索有关可能改善的复杂性理论限制。令人满意的性将为起点提供对其他NP完整问题的确切复杂性（例如旅行推销员问题和K-色情性）的确切复杂性的起点。该提案既解决了最糟糕的表现，又解决了快速算法作为解决此问题的启发式方法。这种探索将主要是数学。但是，当开发新的算法和启发式方法时，将实施它们，并广泛使用所得的软件。这项研究将纳入由PI教授的课程中，包括研究生和本科级别。研究生和本科生都将作为项目的一部分进行研究。