Research Interests
The research interests of the group are mainly in the area of
computational complexity. The current interests can be broadly
described as the following lines of research:
- There are several problems of an algebraic nature that exhibit different computational properties as compared to the usual combinatorial problems. Unlike standard combinatorial problems, algebraic problems like Graph Isomorphism or Integer Factorization do not readily get classified into polynomial-time solvable on the one hand and NP-hard problems on the other. The above examples are problems of deep relevance from both theoretical and practical standpoints. In order to gain a better understanding of the complexity of these problems it is important to investigate their structural properties (as, e.g., completeness or lowness for complexity classes). The group has done sustained work on the structural complexity of graph isomorphism over the years.
- A related research topic of interest is the question whether the use of randomness and/or interaction with a prover (or an oracle) admits more efficient algorithms for certain algorithmic problems. A promising approach is to investigate the relationships between complexity classes that are defined on the basis of different models of computation as, e.g., Turing machines, interactive proofs, or combinatorial circuits. Along this line of research we are interested in the question whether NP-complete problems are computable by polynomial size circuits. The above issues are also broadly related to learning theory questions for specific concept classes.
- Other research interests of the group are in the areas of algorithmic learning theory and in cryptography. These are areas with foundations in complexity theory, and build on notions and methods from complexity theory. Following connections mentioned in the previous paragraph, our research goal here is to explore applications of complexity concepts to query learning as well as PAC learning. Relatedly, we have established a close connection between the existence of cryptographically secure pseudorandom generators and distribution-specific learning. In a more practically oriented research project on cryptography, we are currently exploring a formal security model for an electronic signature application.
- There is also a well-known connection between complexity theoretic questions (like NP =? coNP) and length bounds for proof systems in propositional logic. Related to the latter is the question whether there exist optimal proof systems for the set of tautologies or for other languages. Here, recent work in the group indicates a close connection to the purely complexity-theoretic question, whether certain promise classes (like NP ∩ co-NP) have complete problems.
- Finally, a recent interest in the group is to seek applications of the parameterized complexity paradigm in areas like algorithmic learning and cryptography.
Research Projects
Research Seminar