Consistency of circuit lower bounds with bounded theories

MaRDI QIDQ5114830FDOQ5114830

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

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

Mathematics Subject Classification ID

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

Cited In (6)

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

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)