PhD Position: ERC Advanced Grant 339691
This project aims at making progress in the study of basic open problems in computational complexity, such as the P versus NP problem. There are several approaches to these difficult problems, one of which is proof complexity. In proof complexity we not only study the lengths of proofs in various proof systems, but also first order theories associated with complexity classes, collectively called bounded arithmetic. Proving separations between proof systems or theories in bounded arithmetic, however, seems as difficult as separating the corresponding complexity classes.