Limits of minimum circuit size problem as oracle

DOI10.4230/LIPICS.CCC.2016.18MaRDI QIDQ5368752zbMATH OpenFDO

Authors Shuichi Hirahara, Osamu Watanabe

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2016.18

zbMATH Keywords

minimum circuit size problemNP-completenessrandomized reductionsresource-bounded Kolmogorov complexityTuring reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• The minimum oracle circuit size problem
• The Minimum Oracle Circuit Size Problem.
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity
• The non-hardness of approximating circuit size

Cited in

(32)

• Circuit size relative to pseudorandom oracles
• Hardness of sparse sets and minimal circuit size problem
• Discrete logarithm and minimum circuit size
• The minimum oracle circuit size problem
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• The Minimum Oracle Circuit Size Problem.
• The Complexity of Complexity
• Minimum circuit size, graph isomorphism, and related problems
• On nonadaptive reductions to the set of random strings and its dense subsets
• On the (non) NP-hardness of computing circuit complexity
• Minimum circuit size, graph isomorphism, and related problems
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• The power of natural properties as oracles
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• The final nail in the coffin of statistically-secure obfuscator
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-tape Turing machine and branching program lower bounds for MCSP
• 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
• One-tape Turing machine and branching program lower bounds for MCSP
• Lifting for constant-depth circuits and applications to MCSP

This page was built for publication: Limits of minimum circuit size problem as oracle

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