The goal of my talk will be to present some results on the power of various proof systems for the graph isomorphism problem and the constraint satisfaction problem. In order to do so I will give a short introduction to proof complexity, discuss different relaxations of the graph isomorphism problem and the algebraic approach to the constraint satisfaction problem. No prior knowledge on any of those topics is required.