Our Research Activities in Computational Complexity
Computational complexity is the heart of complexity theory. It aims to characterize computational resources needed to solve given compuational problems. While in algorithm design the focus is laid on the design of possibly efficient solutions, in computational complexity one tries to analyse bounds on the minimum of a computational resource (time, space, communication, ...) needed to solve the problem.
Our work in this research field was primarily devoted to the investigation of the following problems:
- Investigation of the circuit (model) complexity. Here, we investigate bounds on resource requirements (so-called lower and upper bounds) for the computation of specific problems by means of circuits and similar computation models, like branching programs. In particular we proved lower bounds on various types of branching programs and investigate the interdependance between certain resources of circuits and branching programs on one hand and requirements for communication in distrubuted computations on the other.
- 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
- Team leader:
- Former members:
- Dipl.-Inf. Volker Klotz
- 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 Dr. Stasys Jukna (now with Uni Frankfurt)
- Dr. Anna Slobodova (now with Compaq, Shrewsbury/USA)
- Dr. Jordan Gergov (now with MPI Saarbrücken)
Publications
Other Activities:
- Christoph Meinel acts as the Editor-in-Chief of ECCC, the Electronic Colloquium on Computational Complexity. Members of the research group work as local office of ECCC
- We coordinated the "Theorietag", a serious of workshops on complexity theory.
- In 2003, we organized the 6th International Symposium on Representations and Methodology of Future Computing Technologies - RM 2003
- In 1999, we organized the famous international STACS-conference
