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

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

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.