Circuit lower bounds in bounded arithmetics

Annals of Pure and Applied Logic 166 (1):29-45 (2015)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2014.08.004

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,369

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Feasibly constructive proofs of succinct weak circuit lower bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.
Lower complexity bounds in justification logic.Samuel R. Buss & Roman Kuznets - 2012 - Annals of Pure and Applied Logic 163 (7):888-905.
Some lower bounds on Shelah rank in the free group.Javier de la Nuez González, Chloé Perin & Rizos Sklinos - 2020 - Annals of Pure and Applied Logic 171 (6):102794.
Computational complexity for bounded distributive lattices with negation.Dmitry Shkatov & C. J. Van Alten - 2021 - Annals of Pure and Applied Logic 172 (7):102962.
On lengths of proofs in non-classical logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.
Erratum to “Ordinal notations and well-orderings in bounded arithmetic” [Annals of Pure and Applied Logic 120 (2003) 197–223]. [REVIEW]Arnold Beckmann, Samuel R. Buss & Chris Pollett - 2003 - Annals of Pure and Applied Logic 123 (1-3):291.
Jan Krajíèek.Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52:143-153.
On bounded functional interpretations.Gilda Ferreira & Paulo Oliva - 2012 - Annals of Pure and Applied Logic 163 (8):1030-1049.
Upper bounds for the arithmetical degrees.M. Lerman - 1985 - Annals of Pure and Applied Logic 29 (3):225-254.
Low upper bounds in the LR degrees.David Diamondstone - 2012 - Annals of Pure and Applied Logic 163 (3):314-320.

Analytics

Added to PP
2015-08-28

Downloads
15 (#1,241,352)

6 months
4 (#1,264,753)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Feasibly constructive proofs of succinct weak circuit lower bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.

Add more citations

References found in this work

Bounded arithmetic and the polynomial hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.

View all 7 references / Add more references