Computational Complexity

Within the research field of Computational Complexity, problems from a main research field in the theoretical computer science, namely, the characterization of resource requirements - in particular, the minimum resource requirements - were analyzed for specific computations.

Work in this research field was primarily devoted to the investigation of the following problems:

• Investigation of the circuit complexity. Here, bounds on resource requirements (so-called lower and upper bounds) for the computation of specific problems by means of circuits and similar computation models have been investigated. In this case, the interdependance between the requirement for computational resources of such models and the communication requirements was of special importance.

• Characterization of the communication complexity in the case of distributed computation of specific problems. Here, important information about the minimum resource requirements for specific computations could be obtained.

• Investigation of the complexity of proof systems. Here, problems which are becoming more significant with raising availability of increasingly ``intelligent'' computer systems were analyzed. Dependencies between structures of problems and computations were of great importance.

People

• Director:
  • Prof. Dr. Christoph Meinel
• Staff members:
  • Dipl.-Inf. Volker Klotz
• Former members:
  • Dr. Rustam Mubarakzjanov(now with Kazan University)
  • Prof. Dr. Martin Mundhenk (now with Uni Jena)
  • PD Dr. Carsten Damm (now with Uni Göttingen)
  • PD. Stasys Jukna(now with Uni Frankfurt)
  • Anna Slobodova (now with Compaq, Shrewsbury/USA)
  • Jordan Gergov (now with MPI Saarbrücken)
• List of technical reps:
• Further Activities:
  • GI-Fachgruppe "Komplexität"
  • ECCC
  • Theorietag

  ---

  
  TCS+NA Research Page - webmaster - 30-May-2001