Constant depth formula and partial function versions of MCSP are hard

DOI10.1137/20m1383562MaRDI QIDQ6654556

Rahul Ilango

Publication date: 20 December 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

exponential time hypothesiscircuit lower boundsminimum circuit size problemminimum formula size problem\(\mathsf{NP}\)-hardnessconstant depth formulasnatural proofs barrier

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The complexity of Boolean formula minimization
• The new complexity landscape around circuit minimization
• Which problems have strongly exponential complexity?
• Lower bounds on learning decision lists and trees
• The complexity of properly learning simple concept classes
• Circuit minimization problem
• Learning read-once formulas with queries
• A Pseudorandom Generator from any One-way Function
• An Average-Case Depth Hierarchy Theorem for Boolean Circuits
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• Computational Complexity
• Learning algorithms from natural proofs
• Slightly Superexponential Parameterized Problems
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Natural proofs
• On the complexity of \(k\)-SAT

This page was built for publication: Constant depth formula and partial function versions of MCSP are hard