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