Limits of minimum circuit size problem as oracle
DOI10.4230/LIPICS.CCC.2016.18zbMATH Open1380.68240MaRDI QIDQ5368752FDOQ5368752
Authors: Shuichi Hirahara, Osamu Watanabe 
Publication date: 10 October 2017
Recommendations
NP-completenessminimum circuit size problemTuring reductionsrandomized reductionsresource-bounded Kolmogorov complexity
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cited In (23)
- Title not available (Why is that?)
- Discrete logarithm and minimum circuit size
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- The Complexity of Complexity
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- The final nail in the coffin of statistically-secure obfuscator
- Hardness of sparse sets and minimal circuit size problem
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- Title not available (Why is that?)
- The power of natural properties as oracles
- One-tape Turing machine and branching program lower bounds for MCSP
- Title not available (Why is that?)
- The Minimum Oracle Circuit Size Problem.
- Circuit size relative to pseudorandom oracles
- On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
- Title not available (Why is that?)
- The non-hardness of approximating circuit size
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
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)
