Complexity of Equational Proof Systems

 COMPUTER SCIENCE/DISCRETE MATH II Topic: Complexity of Equational Proof Systems Speaker: Pavel Hrubes Affiliation: Member, School of Mathematics Date: Tuesday, November 18 Time/Room: 10:30am - 12:30pm/S-101

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.)