Preprint:

    Arnold Beckmann and Sam Buss
    "On Transformations of Constant Depth Propositional Proofs"
    Annals of Pure and Applied Logic 170, 10 (2019) 1176-1187.

    Download preprint.

Abstract: This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.

Back to Sam Buss's publications page.