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

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

• 批准号: 1213151
• 负责人: Russell Impagliazzo
• 金额: $ 125万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1213151&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, fromminimizing circuits in VLSI to verifying hardware and software tomachine learning. Lower bound proofs show that computational problemsare difficult in the sense of requiring a prohibitiveamount 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 breaka code. Surprisingly, recent research by the PIs and othersshows 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 todesign new meta-algorithms and to prove new lower bounds.A primary focus will be on meta-algorithms fordeciding if a given algorithm is 'trivial' or not, such as algorithmsfor the Boolean satisfiability problem. The proposed research will devise newalgorithms that improve over exhaustive search for many variantsof satisfiability. On the other hand, it will also explorecomplexity-theoretic limitations on how much improvement ispossible, using reductions and lower bounds for restrictedmodels. Satisfiability will provide a starting point for a moregeneral understanding of the exact complexities of other NP-completeproblems such as the traveling salesman problem and k-colorability.The proposal addresses both worst-case performance and the useof fast algorithms as heuristics for solving this problem.This exploration will be mainly mathematical. However, whennew algorithms and heuristics are developed, they will beimplemented and the resulting software made widely available.This research will be incorporated in courses taught bythe PI's, at both graduate and undergraduate levels.Both graduate and undergraduate students will perform researchas part of the project.

元算法是将其他算法作为输入的算法。META-ALGORITHMS在各种应用中很重要，可以从VLSI中的电路汇总以验证硬件和软件Tomachine学习。较低的证据表明，在需要时间，内存或其他资源来解决的意义上，计算问题很难解决。在密码学的背景下，这一点尤为重要，在密码学的背景下，确保没有可行的对手可以破坏代码至关重要。令人惊讶的是，在正式的意义上，PIS和其他节目的最新研究表明，设计元算法的研究等同于证明下限。换句话说，可以通过正（设计新的元算法）来证明一个负面（小电路的不存在以解决问题）。 这是Pi Williams突破的关键，在恒定的深度电路上证明了下界的下限。拟议的研究将利用这一联系。 问题。 拟议的研究将设计出新的Algorithms，以改善对许多可满足性的详尽搜索。 另一方面，它还将使用限制模型的减少和下限来探索有关改进的可能性的限制。令人满意的性将为开普通的理解，以了解其他NP解决问题的确切复杂性，例如旅行推销员问题和K-透明度。该提案既解决最差的表现，又解决了快速算法的使用，因为可以解决此问题。 但是，当开发新的算法和启发式方法时，它们将进行大修，并将其最终可用的软件进行。这项研究将在PI的课程中纳入研究生和本科级别。毕业生和本科生都将在该项目的研究中进行研究。