Division of Computing and Communication Foundations
Algorithmic Foundations (AF)
See program guidelines for contact information.
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. 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, social networks, 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. Algorithmic research on problems arising from areas including databases, machine learning, data mining, robotics, computer vision, networks, communications, operating systems, computer memory models, programming languages, compilers, and machine abstractions is supported. 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. In these cases, 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.
Research that incorporates significant activity in both algorithmic theory and practice is generally supported through other, cross-cutting programs. Some examples are Critical Techniques, Technologies, and Methodologies for Advancing Foundations and Applications of Big Data Sciences & Engineering (BIGDATA); Integrative Strategies for Understanding Neural and Cognitive Systems (NSF-NCS); National Robotics Initiative 2.0: Ubiquitous Collaborative Robots (NRI-2.0); Secure and Trustworthy Cyberspace (SaTC); and Smart and Connected Health: Connecting Data, People, and Systems (SCH).
Funding Opportunities for the Algorithmic Foundations Program: