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