Division of Computing and Communication Foundations
Algorithmic Foundations (AF)CONTACTS
See program guidelines for contact information.
The Algorithmic Foundations (AF) program supports potentially transformative research and education projects advancing design and analysis of algorithms and characterized by algorithmic thinking accompanied by rigorous analysis. Research on algorithms for problems that are central to computer science and engineering, as well as new techniques for the rigorous analysis of algorithms, are of interest. AF supports theoretical research that bounds the intrinsic difficulty of problems to determine the 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. The time and space complexity of finding exact and approximate solutions in deterministic and randomized models of computation is a central concern of the program; research on resources other than time and space, such as communication and energy, is also encouraged. In addition to the traditional, sequential computing paradigm, AF supports research on the design and analysis of novel algorithms in parallel and distributed models, in particular, in heterogeneous multi-core and many-core machines; the computational models and algorithms that capture essential aspects of computing over massive data sets; and alternative forms of computation and information processing, including quantum computing and biological models of computation.
The program supports research in algorithms needed in all areas, both within and outside computer science. Algorithmic research with applications in databases, machine learning, data mining, networks, communications, operating systems, languages, compilers, and machine abstractions is supported. New techniques for the design and analysis of algorithms in areas such as optimization, cryptography, computational geometry, computational biology, game theory, social networks, and numeric, symbolic, and algebraic computing are appropriate for this program. Relevance to application areas is important and collaborations with researchers in those areas are encouraged. However, research funded by this program must advance the study of algorithms. When accompanied by rigorous analysis of computational resource requirements and/or algorithmic performance measures, projects with an implementation component are also considered.
Research that incorporates significant activity in both theory and practice is supported through cross-cutting programs. CCF/AF leads Algorithms in the Field (AitF, http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=505125), which is particularly interested in developing and supporting collaboration between theory researchers and those in more applied areas. See other NSF cross-cutting programs for theory and applications in Big Data; Brain Science; Food, Energy & Water Systems; Secure and Trustworthy Cyberspace; Smart & Connected Health; etc. (http://www.nsf.gov/funding/pgm_list.jsp?org=CISE)
More information on topics appropriate for the Algorithmic Foundations program is available at:
Funding Opportunities for the Algorithmic Foundations Program: