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

点击翻译按钮获取中文摘要

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.