Circuit lower bounds from NP-hardness of MCSP under turing reductions

DOI10.4230/LIPIcs.CCC.2020.26OpenAlexW3046490946MaRDI QIDQ5092477

Rahul Santhanam, Michael E. Saks

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.26

zbMATH Keywords

circuit lower boundsminimum circuit size problemTuring reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

The power of natural properties as oracles ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Robust simulations and significant separations
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Zero Knowledge and Circuit Minimization
• The Minimum Oracle Circuit Size Problem.
• The Complexity of Complexity
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Circuit minimization problem
• Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Computational Complexity
• On the Computational Complexity of Algorithms
• Power from Random Strings

This page was built for publication: Circuit lower bounds from NP-hardness of MCSP under turing reductions