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