Circuit lower bounds in bounded arithmetics
type: Item
instance of: scholarly article
title: Circuit lower bounds in bounded arithmetics
zbMATH Open document ID: 1341.03088
author: Ján Pich
published in: Annals of Pure and Applied Logic
publication date: 2014-10-27T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 6361697
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: circuit lower bounds
MaRDI profile type: Publication
full work available at URL: j.apal.2014.08.004
OpenAlex ID: W2054191060
cites work: Q3800030
cites work: Q4133141
cites work: Consequences of the provability of NP ⊆ P/poly
cites work: Q4375756
cites work: Q5306365
cites work: Dual weak pigeonhole principle, Boolean complexity, and derandomization
cites work: Approximate counting in bounded arithmetic
cites work: An arithmetical characterization of NP
cites work: Q4010360
cites work: Q4856172
cites work: Q4381413
cites work: ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
cites work: Bounded arithmetic and the polynomial hierarchy
cites work: Hardness vs randomness
cites work: Q4010368
cites work: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
cites work: Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
DOI: 10.1016/J.APAL.2014.08.004
description: scientific article; zbMATH DE number 6361697