The Minimum Oracle Circuit Size Problem.
From MaRDI portal
Recommendations
- The minimum oracle circuit size problem
- Limits of minimum circuit size problem as oracle
- On the NP-Completeness of the Minimum Circuit Size Problem.
- scientific article; zbMATH DE number 7250145
- Approximability of Minimum AND-Circuits
- Approximability of minimum AND-circuits
- Minimum circuit size, graph isomorphism, and related problems
- Minimum circuit size, graph isomorphism, and related problems
- The Minimum Satisfiability Problem
- scientific article; zbMATH DE number 4125012
Cited in
(13)- Discrete logarithm and minimum circuit size
- The minimum oracle circuit size problem
- The Complexity of Complexity
- \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- CNF and DNF succinct graph encodings
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Limits of minimum circuit size problem as oracle
- The power of natural properties as oracles
- The final nail in the coffin of statistically-secure obfuscator
- Lifting for constant-depth circuits and applications to MCSP
This page was built for publication: The Minimum Oracle Circuit Size Problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954981)
