Constant depth formula and partial function versions of MCSP are hard

DOI10.1109/FOCS46700.2020.00047MaRDI QIDQ6944009zbMATH OpenFDO

Authors Rahul Ilango

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00047

Mathematics Subject Classification ID

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

Cited in

(6)

• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Regularization of low error PCPs and an application to MCSP
• Lower bounds for Levin-Kolmogorov complexity
• Lifting for constant-depth circuits and applications to MCSP
• SAT reduces to the minimum circuit size problem with a random oracle

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

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