Date & Time: Wednesday, October 29, 2014, 16:00-17:00.
Venue: Ramanujan Hall
Speaker: Nutan Limaye, IIT Bombay
Title: Proof complexity and proof systems
Abstract: Consider the following simple problem: given a set of linear inequalities, decide whether it has a feasible solution or prove that there is no feasible solution for it. How easy or hard is this problem? How does one quantify the easiness or hardness of this problem? Such questions are central to the the field of proof complexity.
In this talk, we will give a brief introduction to the field of proof complexity. This is the area of theoretical computer science which classifies mathematical statements based on the lengths of the proofs required to prove them and the resources required to verify the correctness of the alleged proofs.
We will start the talk with a few motivating examples. We will then introduce the notion of a proof system, which allows us to perform a systematic study of proofs. We will look at different types of proof systems and give a list of known results. We will end the talk with a list of open problems.