|
Algorithmic Foundations
(AF)
CONTACTS
See program guidelines for contact information.
SYNOPSIS
The Algorithmic Foundations program supports research characterized by algorithmic thinking accompanied by rigorous analysis. 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. 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 of computing such as, parallel and distributed models are welcomed. Such research includes optimizations across complex processor/memory hierarchies. Quantum computing, error correction, and techniques for dealing with decoherence are of interest.. The program also supports rigorous work in experimental algorithmics in all of these models that relies on hypothesis formulation, experiment design, observation, modeling, and prediction in arriving at an understanding of algorithm behavior. The program supports research in algorithms needed in other areas both within and outside computer science. Algorithmic research in databases, networks, communications, 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 symbolic methods include symbolic constraint satisfaction problems. Hybrid numeric-symbolic-algebraic methods in support of multi-scale, multi-grid methods and computation on peta-scale machines are also welcome. 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. More information on topics of interest within the program is available at: http://www.nsf.gov/cise/ccf/af_pgm09.jsp Algorithmic Foundations (AF) Staff Funding Opportunities for the Algorithmic Foundations Program: Computing and Communication Foundations (CCF): Core Programs. NSF 09-555
THIS PROGRAM IS PART OF
Computing and Communication Foundations (CCF): Core Programs
|
