Consistency of circuit lower bounds with bounded theories

MaRDI QIDQ5114830zbMATH OpenFDO

Authors J. Bydžovský, Jan Krajíček, Igor C. Oliveira

Publication date 26 June 2020

Full work available at URL https://arxiv.org/abs/1905.12935, https://lmcs.episciences.org/6576

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Circuit lower bounds in bounded arithmetics
• Lower bounds for unrestricted Boolean circuits: open problems
• Proving Circuit Lower Bounds in High Uniform Classes
• Unprovability of circuit upper bounds in Cook's theory PV
• Natural proofs

Cited in

(7)

• Consistency of circuit lower bounds with bounded theories
• Lower bounds: from circuits to QBF proof systems
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Unprovability of strong complexity lower bounds in bounded arithmetic
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• A quasi-lower bound on the consistency strength of PFA
• Approximate counting and NP search problems

This page was built for publication: Consistency of circuit lower bounds with bounded theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114830)