Algorithmic Foundations (AF)

The Algorithmic Foundations (AF) program seeks proposals addressing foundational and transformative computer science and engineering research and education advancing the design and analysis of algorithms, computational complexity, and the rigorous experimental study and application of algorithms to other areas within and outside computer science. Broad categories of interest within AF include, but are not limited to:

Algorithms and Complexity. Novel research on algorithm design and questions related to complexity and hardness of resource bounded computation, including:

  • Design and analysis of algorithms: deterministic and randomized, optimal and approximate with performance analysis and approximation guarantees, on-line algorithms, sublinear and streaming, energy-efficient, parallel and distributed, scalabe algorithms for multi/many-core environments, and memory-aware algorithms.
  • Combinatorial and graph-theoretic algorithms: algorithms for classical and new problems, as well as mathematical results in combinatorics with application to algorithm design.
  • Computational and communication complexity: new techniques, completeness, reductions, relation between complexity classes, new complexity measures, inapproximability, cryptograpthy and randomness.
  • Data structures: abstract data types, analysis of classical and new data structures, distributed data structures, data structure for massive data sets.
  • Numeric, symbolic, algebraic algorithms for scientific computation: correctness proofs, smoothed analysis, randomized algorithms, symbolic constraint satisfaction, hybrid numeric-symbolic computation.
  • Optimization: algorithms with rigorous analysis for linear, convex, and non-linear programming; applications of optimization techniques to combinatorial problems.

Algorithms in the Field. Novel research focused on the development and analysis of algorithms in fields, both inside and outside of computer science that advance algorithmic understanding:

  • Algorithms for applications in other areas of computer science such as artificial intelligence, computer and network security, languages and compilers, databases, networks and operating systems, robotics and machine vision, sensor networks and mobile devices, the World Wide Web including the "deep web," social networking systems, cloud computing.
  • Computational geometry: geometric algorithms accompanied by rigorous analysis, algorithms with applications to graphics, robotics and others.
  • Cryptography: primitives for privacy, confidentiality, authentication, new protocols, algorithms to break cryptosystems, post-quantum cryptography, side channel attacks, connections with computational complexity.
  • Machine learning and data analytics: new algorithmic techniques accompanied by rigorous analysis with a particular emphasis on algorithms targeted at massive data sets.
  • Computational biology: understanding biological systems via modeling, simulation and algorithm design, developing techniques and methodologies to gain knowledge about biological systems in their entirety, including protein structure, gene and protein network discovery, sequence analysis.
  • Computational sustainability: novel algorithms for problems addressing sustainability challenges in our society.

Emerging and Alternate Models of Computing. Research on computational models motivated by novel or emerging computing technologies, as well as moving beyond evolutionary technological advances to innovations that enable fundamentally different ways of computing.

  • Quantum information science: new algorithms for computation and communication, their complexity, quantum information, study of entanglement, decoherence, error correction and quantum information processing.
  • New theories and models of computation that exploit biological properties or similarities in biological network structures.
  • Other models of computation and relationships between them: automata, adaptive, data driven, distributed, hybrid, online, parallel, probabilistic, quantum, reactive, sequential, streaming.