# Mathematical Conversations

**Topic: **How deep is your proof?

**Speaker: **Toniann Pitassi

**Affiliation: **University of Toronto; Visiting Professor, School of Mathematics

**Date & Time: **Wednesday October 25th, 2017, 6:00pm - 7:00pm

**Location: **Dilworth Room

There is a very short proof that a graph is 3-colorable: you simply give the coloring - it is linear in the size of the graph. How long a proof is needed that a given graph is *not* 3-colorable? The best we know is exponential in the size of the graph. Proving that there is no polynomial-length proof is the holy grail of proof complexity, the field I will describe in this talk. I will give concrete examples of *simple* proof systems from several domains (graph theory, algebra, logic), and explain the importance of proving lower bounds for these systems, and the connection to P vs NP.