Leader of the group Algorithms and Complexity (A&C, was PNA6): Harry Buhrman.

There is great progress and opportunity in nonclassical computational technologies and algorithmics. These include exploiting novel computational aspects of physical phenomena, using nonclassical algorithms, or using classical algorithmics in a nonclassical manner. Key issues are feasibility of technology, efficiency of algorithms, and theoretical basics.

Novel technologies comprise coherent quantum mechanical and reversible low-energy computing. Example nonclassical improvements by quantum computing are:

• Fast factoring (compromising current cryptosystems;) and
• Square-root unordered search (enabling to quickly search unstructured databases.)
• Better-than-classical communication complexity in computing certain functions by two or more parties (work done at CWI.)
• Reversible computing is the only known technology to enable continuing advances in computing power by miniaturization in the medium long term (15-20 years) and mobilization of computing in the short term.

Novel aspects of classical algorithms include

• distributed networking, security,
• bio-informatics algorithmics and
• automatic learning by compression.

The work programme in quantum algorithmics includes the design and analysis of new algorithms in the communication and the ``black box'' model, and development of new tools to establish complexity bounds of such algorithms. We plan to test such algorithms collaborating with experimental groups in the USA. In reversible computing we develop new reversible simulations that simultaneously use less time and memory than any currently known algorithm. In machine learning we continue our work on algorithmic minimal sufficient statistics and minimal description length learning (MDL). Applications of algorithmic information theory (aka Kolmogorov complexity) in mathematics and algorithms are investigated and consolidated in a 3rd edition of the related textbook. A new research strain (for the moment part of INS4.3) is planned and started in theoretical analysis and applications of computational biology. In particular in sequencing, analyzing genomic material in secondary and tertiary structure.

Some former group members
Rudi Cilibrasi, Wim van Dam, Lance Fortnow, Peter Gacs, Jaap-Henk Hoepman, Hartmut Klauck, Michal Koucký, Troy Lee, Zvi Lotker, Hein Röhrig, Steven de Rooij, Nitin Saxena, Robert Spalek, Barbara Terhal, Ben Toner, John Tromp, Falk Unger, Stephanie Wehner.