[iasmath-seminars] Reminder for tonight's Mathematical Conversation

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Mathematical Conversations
Wednesday, October 25

***Please note that Harry's Bar is closed tonight. Drinks will be available in the Dilworth Room.

About Mathematical Conversations: We meet in Harry's Bar at 6pm, where free drinks are provided. After 20 minutes, we move to the Dilworth room, where the speaker gives a 20-minute talk, followed by 15 minutes of discussion with the audience. After that we return to the bar for further discussions. Website:https://www.math.ias.edu/math-conversations

To view mathematics in titles and abstracts, please click on the talk's link.


Topic: 		How deep is your proof?
Speaker: 	Toniann Pitassi, University of Toronto; Visiting Professor, School of Mathematics
Time/Room: 	6:00pm - 7:00pm/Dilworth Room
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=131213

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.

http://www.math.ias.edu/seminars