CCF: Algorithmic Foundations (AF)

The Algorithmic Foundations (AF) program supports potentially transformative projects in the theory of algorithms. Projects should be characterized by algorithmic innovation accompanied by rigorous analysis. Of interest is research on algorithms for problems that are central to computer science and engineering, as well as new techniques for the rigorous analysis of algorithms and computational complexity. AF supports theoretical research that bounds the intrinsic difficulty of problems to determine measures of complexity in formal models of computation, classical or new. The goal is to understand the fundamental limits of resource-bounded computation and to obtain efficient algorithms operating within those limits. Research on resources other than the traditional time and space measures, such as communication and energy, is also encouraged, as is research on tradeoffs between resource use and solution quality, such as running time vs. approximation error. Rigorous analysis of properties of algorithms relating to fairness, ethics, accountability, transparency, and privacy is also in scope. In addition to the traditional sequential-computing paradigm, AF supports research on the design and analysis of novel algorithms in parallel and distributed models, as well as computational models and algorithms that capture essential aspects of computing over massive data sets.

New techniques for the design and analysis of algorithms and analysis of problem complexity in areas such as optimization, cryptography, computational geometry, game theory and economics, social networks, machine learning, and numeric, symbolic, and algebraic computing are within the scope of this program. The program also supports research in algorithms needed in applied areas of research, including algorithmic research on problems arising in other areas of research on computing. While relevance to application areas is important and collaboration with researchers in these areas is encouraged, research funded by this program must advance the theoretical study of algorithms. When accompanying rigorous analysis of computational resource requirements and/or algorithmic performance measures, implementation efforts and empirical evaluation are considered strong broader impacts. Letters of collaboration from applied researchers are encouraged.

Emerging topics such as quantum computing and biological models of computation are now addressed in the Foundations of Emerging Technologies (FET) program. However, projects in these areas focused on foundational issues of algorithms and complexity in these topics, as described above, can also be considered by the AF program.