[Proof Complexity] New paper on Bounded Arithmetic and Pigeonhole Principle

[Mykyta Narusevych]

Dear colleagues,
I have a new paper regarding unprovability of the pigeonhole principle inside fragments of bounded arithmetic,  see https://arxiv.org/abs/2208.14713.
  In particular, we prove that the theory T_2^1(R) extended by instances of the weak pigeonhole principle for polynomial-time predicates with oracle access to R is not able to prove that R itself does not violate the usual pigeonhole principle. The proof in the paper avoids switching lemma and relies upon the forcing technique only.
  We also achieve the following result: the theory T_2^1(R) extended by instances of the pigeonhole principle up to n^{1 - \epsilon} for polynomial-time predicates with oracle access to R is not able to prove a pigeonhole principle up to n stated for R.  This can be seen as a step towards an open problem first stated by M. Ajtai.
With regards,
Narusevych Mykyta