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

元算法是将其他算法作为输入的算法。元算法在各种应用中都很重要，从最小化VLSI电路到验证硬件和软件再到机器学习。下界证明表明，计算问题在需要大量时间、内存或其他资源来解决的意义上是困难的。这在密码学的上下文中尤其重要，因为确保没有可行的对手可以破解代码是至关重要的。令人惊讶的是，pi和其他人最近的研究表明，在正式意义上，设计元算法相当于证明下界。换句话说，一个人可以通过一个积极的（设计一个新的元算法）来证明一个消极的（不存在一个解决问题的小电路）。这是PI Williams取得突破的关键，他用模算术门证明了定深电路的下界。提出的研究将利用这种联系来设计新的元算法并证明新的下界。主要焦点将放在决定给定算法是否“平凡”的元算法上，例如布尔可满足性问题的算法。提出的研究将设计新的算法，以改进对许多变量满意度的穷举搜索。另一方面，它也将探索复杂性理论的限制，多大程度的改进是可能的，使用限制模型的约简和下界。可满足性将为更广泛地理解其他np完全问题（如旅行推销员问题和k-可色性）的确切复杂性提供一个起点。该方案解决了最坏情况下的性能和使用快速算法作为启发式方法来解决这个问题。这个探索将主要是数学上的。然而，当新的算法和启发式被开发出来时，它们将被实现，并且由此产生的软件将被广泛使用。这项研究将被纳入PI教授的研究生和本科生课程中。作为项目的一部分，研究生和本科生都将进行研究。

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.