Bounded arithmetic is a collective name of fragments of Peano arithmetic that are closely related to complexity classes, such as P, PH, and L. The study of bounded theories is relevant to the program of showing unprovability of complexity conjectures; moreover, the techniques in this field are found useful in complexity theory and cryptography. In this reading group, we will learn basics of bounded arithmetic from scratch (without assuming backgrounds in logic).
Organizer: Jiatu Li