Sublogarithmic uniform Boolean proof nets

Clément Aubert
(LIPN - UMR7030 CNRS - Université Paris 13)

Using a proofs-as-programs correspondence, Terui was able to compare two models of parallel computation: Boolean circuits and proof nets for multiplicative linear logic. Mogbil et. al. gave a logspace translation allowing us to compare their computational power as uniform complexity classes. This paper presents a novel translation in AC0 and focuses on a simpler restricted notion of uniform Boolean proof nets. We can then encode constant-depth circuits and compare complexity classes below logspace, which were out of reach with the previous translations.

In Jean-Yves Marion: Proceedings Second Workshop on Developments in Implicit Computational Complexity (DICE 2011), Saarbrücken, Germany, April 2nd and 3rd, 2011, Electronic Proceedings in Theoretical Computer Science 75, pp. 15–27.
Published: 1st January 2012.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: