[Proof Complexity] New paper

[Albert Atserias]

Dear Friends and Colleagues,

We are pleased to announce a new manuscript:

Title: The Ordering Principle in a Fragment of Approximate Counting.

Authors: Albert Atserias and Neil Thapen. 

Abstract: The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\T^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk and Thapen, 2012] and completes their program to compare the strength of Je\v{r}\'abek's bounded arithmetic theory for approximate counting with weakened versions of it.

URL: http://www.lsi.upc.edu/~atserias/papers/fragment-of-apc/fragment-of-apc.pdf

Best regards,
Albert