Tutorial sessions for the Proof Complexity workshop

Tutorial courses will be held on the two days immediately preceding the workshop.

Sunday, May 15, 2016
   Morning and afternoon sessions:
      Speaker: Sam Buss, University of California, San Diego
      Topics: Bounded arithmetic, proof complexity, and NP search problems.

Monday, May 16, 2016
   Morning and afternoon sessions:
      Speaker: Toniann Pitassi, University of Toronto
      Topics: Propositional Proof Systems, and Algebraic and Semi-algebraic proof systems.

Abstracts

Sam Buss
Bounded arithmetic, proof complexity, and NP search problems.

Abstract: This tutorial will cover first- and second-order theories of bounded arithmetic, translations from bounded arithmetic to propositional proof systems, and associated NP search functions.

Toniann Pitassi
Propositional Proof Systems, and Algebraic and Semi-algebraic proof systems.

Abstract: This tutorial will cover propositional proof systems, and then algebraic and semi-algebraic systems, focusing on lower bound methods and state of the art results thus far, and open problems and barriers. It will cover algebraic systems (including Nullstellensatz, PC, IPS) and semi-algebraic ones (CP, SA, SOS), as well as progress on standard propositional proof systems and some surprising upper bounds.