Anupam Das mini course "Bounded Arithmetic and Proof Complexity" (September 13–21, 2023, Steklov Mathematical Institute, Room 110 + online, Moscow)
In this mini course I will survey some of the basics of bounded arithmetic, as well as its connections to proof and computational complexity. I will focus mainly on the case of polynomial time, starting with Cobham's famous characterisation of polynomial time, thence it's extensions to a quantifier free theory (Cook's PV) and a fragment of arithmetic (Buss' $S^1_2$). I will explain the connection to the Extended Frege system for propositional logic, yielding a uniform-nonuniform correspondence at the level of proof complexity. Finally, I will survey extensions for the polynomial time hierarchy, second order theories, and/or Paris-Wilkie style translations, depending on time available.
Organizer
Das Anupam, University of Birmingham |
|
Anupam Das mini course "Bounded Arithmetic and Proof Complexity", Moscow, September 13–21, 2023 |
|
|
September 20, 2023 (Wed) |
|
1. |
Lecture 1. Bounded Arithmetic and Proof Complexity A. Das September 20, 2023 16:00–17:30, Moscow, Steklov Mathematical Institute, Room 110 + online
|
|
|
|
|
|
September 21, 2023 (Thu) |
|
2. |
Lecture 2. Bounded Arithmetic and Proof Complexity A. Das September 21, 2023 16:00–17:30, Moscow, Steklov Mathematical Institute, Room 110 + online
|
|
|
|
|
|
September 27, 2023 (Wed) |
|
3. |
Lecture 3. Bounded Arithmetic and Proof Complexity A. Das September 27, 2023 16:00–17:30, Moscow, Steklov Mathematical Institute, Room 110 + online
|
|
|
|
|
|
September 28, 2023 (Thu) |
|
4. |
Lecture 4. Bounded Arithmetic and Proof Complexity A. Das September 28, 2023 16:00–17:30, Moscow, Steklov Mathematical Institute, Room 110 + online
|
|
|
|
|
|