Sebastian Müller - Polylogarithmic Cuts in Models of V^0

lmcs:1123 - Logical Methods in Computer Science, April 1, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:16)2013
Polylogarithmic Cuts in Models of V^0Article

Authors: Sebastian Müller

    We study initial cuts of models of weak two-sorted Bounded Arithmetics with respect to the strength of their theories and show that these theories are stronger than the original one. More explicitly we will see that polylogarithmic cuts of models of $\mathbf{V}^0$ are models of $\mathbf{VNC}^1$ by formalizing a proof of Nepomnjascij's Theorem in such cuts. This is a strengthening of a result by Paris and Wilkie. We can then exploit our result in Proof Complexity to observe that Frege proof systems can be sub exponentially simulated by bounded depth Frege proof systems. This result has recently been obtained by Filmus, Pitassi and Santhanam in a direct proof. As an interesting observation we also obtain an average case separation of Resolution from AC0-Frege by applying a recent result with Tzameret.


    Volume: Volume 9, Issue 1
    Published on: April 1, 2013
    Imported on: March 16, 2012
    Keywords: Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • From Mathematical Logic To Applications; Funder: European Commission; Code: 238381

    29 Documents citing this article

    Consultation statistics

    This page has been seen 988 times.
    This article's PDF has been downloaded 143 times.