Karteek Sreenivasaiah
(Institute of Mathematical Sciences, Chennai, India)
Verifying Proofs with Very Little Resources

A proof system for a language L is a function f such that Range(f) is exactly L. One of the main goals of proof complexity is to show that for every proof system computable in polynomial time (w.r.t. output size), there exists a family of tautologies that requires super polynomial length.

We look at proof systems from a circuit complexity point of view and study proof systems that are computationally very restricted. Instead of allowing for polynomial time, we restrict the computational power allowed for computing the proof system to NC0 circuit families. We study the capabilities and weaknesses of NC0 circuit families with respect to computing proof systems for various languages and try to understand their relationship to computational complexity.

In the talk, we will see a lower bound against these restricted proof systems and also some constructions.