Learning Bounded Arithmetic -- A Guide from a Novice

Bounded Arithmetic is a field of mathematical logic which, very roughly, studies subtheories of Peano Arithmetic that "correspond" with reasoning associated with computational complexity classes or propositional proof systems. Correspond here can mean multiple things, but the two most common interpretations would be the prized Witnessing Theorems or Paris-Wilkies Propositional Translations.

At the Simons Institute program for Meta Complexity this winter, many attendants (including myself) wished to learn bounded arithmetic due to its increasing appearances and connections with other areas of complexity. Marco Carmosino, Oliver Korten, and Jan Pich organized a bounded arithmetic reading group to go through many elementary and recent works in bounded arithmetic, with a preference towards those results relating to meta complexity. However, with the creation of the reading group, a running joke was spawned: "I won't define this bounded arithmetic theory"

Every week we would talk about some results in bounded arithmetic, but the speaker would usually not formally define any of the objects discussed! This is because the logical background required to explicitly describe and prove many of these results would have taken a full semester (if not more) to go through. 

Given this, I thought I would outline how I have personally learned this logical background and taught myself some basic bounded arithmetic to boot.

Logical Prerequisites

- Sam Buss - "An Introduction to Proof Theory" is an excellent resource if you start off with no logical         background (like me). 

- Manuel Bodirsky's Model Theory lectures on Youtube

- Richard Kaye - Models of Peano Arithmetic (Chapters I - V)


The order I went through these is reading the first two sections of Sam Buss' Proof Theory handbook, then simultaneously going through the latter two. I highly recommend going slightly further into Kaye's book (Chapters VI - VII), but it isn't absolutely necessary. 

Bounded Arithmetic


- Jan Krajicek - Proof Complexity (select chapters)


An entirely different approach would be to read the book by Cook and Nguyen, "Logical Perspectives in Proof Complexity." This book is self contained and covers both logic and bounded arithmetic. However, I think it is very much worth it to explore the logical prerequisites elsewhere; it is presented here as a means to learn bounded arithmetic rather than a field of its own.  


Unprovability

It is particularly nice, when learning a new subject, to have some papers as a Gatsby-esque green light across the pond to strive to understand. For me, my motivations of learning bounded arithmetic lie strongly with new unprovability results: showing that certain circuit lower bounds are unprovable in theories of bounded arithmetic. These results serve, in my mind, as the ultimate barrier in complexity theory. Below are some papers that I think are worth reading on this topic:





In particular, Carmosino et. al. is a fantastic way to see the utility of witnessing theorems in bounded arithmetic, which give a connection from provability in a theory to algorithms in a complexity class. 





Comments

Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Number-on-the-Forehead Communication Complexity