The new complexity landscape around circuit minimization

DOI10.1007/978-3-030-40608-0_1MaRDI QIDQ782552zbMATH OpenOpenAlexFDO

Authors Eric Allender

Publication date 27 July 2020

Full work available at URL https://doi.org/10.1007/978-3-030-40608-0_1

zbMATH Keywords

complexity theoryKolmogorov complexityminimum circuit size problem

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited in

(8)

• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• New Collapse Consequences of NP Having Small Circuits
• On the complexity of gradient gate circuits
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• Constant depth formula and partial function versions of MCSP are hard
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
• Lifting for constant-depth circuits and applications to MCSP

This page was built for publication: The new complexity landscape around circuit minimization

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