Ricerc@Sapienza

Complexity theory seeks to describe the computational resources which are both necessary and sufficient to resolve a given problem or class of problems in theoretical computer science. The complexity can be measured both in terms of the run-time necessary to resolve the problem (as in algorithmic complexity) or in terms of the proof length for certifying a desired statement, as in proof complexity.

The proposed research follows a two-pronged approach to resolving tight bounds for problems in proof and algorithmic complexity. In the first research theme, the project applies structural graph techniques to give exact characterizations of the classes of input which are algorithmically feasible under a given model of computation for a selection of graph problems. In the second research theme, the project applies algebraic techniques to give new super-polynomial bounds to the necessary proof length for tautologies in various proof systems. The approach to each theme is designed so that progress on one will give new tools and techniques which can be applied to the other.