Circuit lower bounds in bounded arithmetics

DOI10.1016/j.apal.2014.08.004zbMath1341.03088OpenAlexW2054191060MaRDI QIDQ466447

Ján Pich

Publication date: 27 October 2014

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2014.08.004

zbMATH Keywords

bounded arithmeticcircuit lower bounds

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (5)

A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Unnamed Item ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Unprovability of circuit upper bounds in Cook's theory PV

Cites Work

• An arithmetical characterization of NP
• Bounded arithmetic and the polynomial hierarchy
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Hardness vs randomness
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Approximate counting in bounded arithmetic
• Consequences of the provability of NP ⊆ P/poly
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Circuit lower bounds in bounded arithmetics