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