Project Grant 2212233

This four-year, $1.2 million Project Grant from the National Science Foundation's Division of Computing and Communication Foundations will support research in algorithms and complexity for total functions. Funded under the Computer and Information Science and Engineering program, the grant aims to advance understanding of the efficient solvability of important computational problems where a solution is guaranteed to exist, but may still be difficult to find. Specifically, the Columbia University researchers will pursue open complexity questions related to total functions, including the complexity of Tarski fixpoints and unclassified combinatorial problems generalizing the Pigeonhole Principle class PPP. They will also explore new complexity problems linking total functions with cryptography, as well as certain fundamental problems in complexity that arose from their prior study of the class APEPP. In addition, the investigators will examine the capabilities and limitations of black box algorithms for problems in TFNP. The research directly supports NSF's mission to advance computing and communication sciences and is expected to yield findings of intellectual merit and broader impacts.