Iddo Tzameret
Abstract: Theories of Bounded Arithmetic are subtheories of Peano Arithmetic where all axioms have only bounded quantifiers (e.g. Ex\leqt). One of the main motivations for studying Bounded Arithmetic is its close connections with computational complexity theory, in particular questions relating provability in bounded arithmetic to questions about the polynomial time hierarchy.
We shall survey the basics of two principle approaches for dealing with those theories: That of R. Parikh ('71, '73), and that of S. Buss ('85). We shall prove Parikh's Theorem for bounded theories, and if time permits we will also prove a theorem due to Paris and Wilkie ('85) that relates (un)provability in bounded arithmetic to (in)existence of short (polynomial) propositional proofs.
Lecture notes for the talk can be downloaded at: http://www.cs.tau.ac.il/~tzameret/Basic/Bounded/Arithmetic.zip