New insights on the (non-)hardness of circuit minimization and related problems

DOI10.1145/3349616MaRDI QIDQ5205823zbMATH OpenOpenAlexWikidataFDO

Authors Shuichi Hirahara, Eric Allender

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3349616

zbMATH Keywords

circuit sizecomputational complexityKolmogorov complexityMCSP

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) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 7204388
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the average-case complexity of MCSP and its variants

Cited in

(24)

• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Minimum circuit size, graph isomorphism, and related problems
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• On nonadaptive reductions to the set of random strings and its dense subsets
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• New Collapse Consequences of NP Having Small Circuits
• Minimum circuit size, graph isomorphism, and related problems
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• On the average-case complexity of MCSP and its variants
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• On the NP-Completeness of the Minimum Circuit Size Problem.
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Gap MCSP is not (Levin) NP-complete in obfustopia
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Regularization of low error PCPs and an application to MCSP
• Robustness for space-bounded statistical zero knowledge
• On basing auxiliary-input cryptography on NP-hardness via nonadaptive black-box reductions
• Lifting for constant-depth circuits and applications to MCSP
• SAT reduces to the minimum circuit size problem with a random oracle
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: New insights on the (non-)hardness of circuit minimization and related problems

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