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

Post a Comment

Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

-
A classical result from Yannakakis states that $$\text{xc}(P) = \text{rank}_+(S),$$ where \(P\) is a polytope with slack matrix \(S\). Yannakakis further showed that with nondeterministic communication complexity, one can give a lower bound for the nonnegative rank. This lower bound is sufficient to prove that some polytopes, like the correlation polytope, have exponential extension complexity. However, it fails for many other examples.  In a 2013 paper, "Extended formulations, nonnegative factorizations, and randomized communication protocols," by Faenza, Fiorini, Grappe, and Tiwary, they show that a model of randomized communication complexity can not only lower bound nonnegative rank, but exactly characterize it.  In my communication complexity reading group, I gave a talk presenting this paper and its results. The proofs are extremely elegant and simple, making for a very enjoyable read.  For those interested, here is a link to my lecture notes! 
Read more

Google Summer of Code 2020: D-Complete and Mobile Posets

-
In this post, I thought I'd overview the work of  my first paper , which has just recently been accepted to SIDMA.  In order theory, a linear extension of a partially ordered set P is a totally ordered set L which respects the original ordering P. Many famous problems can be converted into counting the number of linear extensions. For example, the number of standard Young tableaux of a given shape is equivalent to the number of linear extensions of a poset with the same shape. Unfortunately, it is #P-complete in general to count linear extensions (even for posets of height 2!). However, there are famous classes of posets like Young diagrams (or more generally, d-complete posets), which have efficient computation. In our paper, we presented a new class of posets called mobiles that have determinant formulas for counting linear extensions and generalize d-complete posets and ribbon posets. Since this past summer converted me into a shut-in, I decided to spend some of that extra ...
Read more