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.
