Algorithmic Foundations  (AF)

SYNOPSIS

The Algorithmic Foundations program supports research characterized by algorithmic thinking accompanied by rigorous mathematical analysis. The goal is to understand the fundamental limits of resource-bounded computation and to obtain optimal solutions within those limits. Specifically, the time and space complexity of finding exact and approximate solutions in deterministic and randomized models of computation are the central concern of the program. Resources other than time and space, such as communication, heat, power, etc., are also of interest. In addition to the traditional, sequential computing paradigm, research on models such as the streaming model, parallel, distributed and hybrid models and the quantum-computing model are welcomed. Such research includes optimizations across complex processor/memory hierarchies as well as measurement of the performance of algorithms by correct, reproducible computational experiments. Theories that exploit algorithmic scalability and portability are especially welcome.

The program also supports research in algorithms that is applicable to other areas both within and outside computer science. Especially welcome are algorithmic applications in databases, networks, operating systems, languages and compilers and machine abstractions. New techniques for the design and analysis of algorithms in areas such as cryptography, computational geometry, computational biology, numerical, symbolic, algebraic, and scientific computing are appropriate for the program. In computational geometry, research can range from theoretical problems to algorithms for applications that arise in computational biology and computer graphics. Numerical methods include recent algorithmic innovations such as smoothed analysis and convergence of geometric algorithms. They also include hybrid numeric-symbolic-algebraic methods in support of multi-scale, multi-grid methods and computation on peta-scale machines. An emerging area of interest lies at the interface of computer science and economics. This program supports research on computing economic equilibria, mechanism design, graphical economic models and other topics in computational game theory and economics. Relevance to the application areas is important and collaborations with researchers in these areas are encouraged. However, research funded by this program must advance the study of algorithms.

In general, research on algorithms for problems that are central to computer science, as well as new techniques for the rigorous mathematical analysis of such algorithms, are solicited. Moreover, there is an interest in theoretical work to bound the intrinsic difficulty of problems to determine the measures of complexity in formal models of computation, classical or new.

More information on topics of interest within the program is available at:
http://www.nsf.gov/cise/ccf/af_pgm.jsp

Algorithmic Foundations (AF) Staff

Funding Opportunities for the Algorithmic Foundations Program:

Computing and Communication Foundations (CCF): Core Programs.  NSF 08-577

THIS PROGRAM IS PART OF

Computing and Communication Foundations (CCF): Core Programs