Since the very beginning of computer science, the efficiency of computation has been a central topic. Concrete applicability of a computational method is heavily influenced by differences in the required resources (e.g. running time and memory space). The field of Computational Complexity studies such differences, and can be considered the dual of research on algorithm. While algorithm research studies ways of solving problems efficiently, computational complexity tries to understand what is the boundary of such exploration. It is not surprise that the two fields are deeply interconnected in meanings and methods.

Computational complexity is an highly dynamic and young field. Major questions have not yet been solved and we aren't even close to spot their weak points. Nevertheless the search of new mathematical tools and strategies brought to light an impressive amount of results about connections with cryptography, interactive systems and the nature of randomness.

We all know that proving theorems is a very difficult task. The point of view of proof complexity is to study the computational issues arising in mathematical logic. The questions of the fields are:

• Do a short proof always exist for a given logical statement?
• Even if a short proof exists… how difficult is to find it?…
• … or to find a proof which is not too much longer?

An immediate observation is that we would like to prove lower bounds on the size of general proofs. Unluckily this is too much to hope for. The field focus to concrete proof systems, which are models and generalizations of theorem provers used in practice. Even in this restricted setting such questions are still relevant.

The study of Computational complexity is part of the broad investigation in theoretical computer science. I am interested in several problems arising in this investigation. I'm also interested in general topics of discrete mathematics like Combinatorics and Graph Theory and Logic.