Computer Science/Discrete Mathematics Seminar II

I will outline the general area of proof complexity, and its traditional problems. I will focus on less traditional ones, namely the complexity of proving identities over certain algebraic structures. The paradigmatic example is a system intended to prove identities f=g, where f,g are algebraic formulas over a particular field, and the question is to estimate lengths of proofs in the system. On one hand, this relates to computational complexity of polynomial identity testing problem, and on the other, to problems in propositional proof complexity. (Joint work with I. Tzameret.)