The Minimum Oracle Circuit Size Problem.

DOI10.4230/LIPIcs.STACS.2015.21zbMath1355.68104OpenAlexW2279489453MaRDI QIDQ2954981

Dhiraj Holden, Valentine Kabanets, Eric W. Allender

Publication date: 24 January 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4901/pdf/1.pdf/

zbMATH Keywords

Kolmogorov complexityPSPACEminimum circuit-size problemNP-intermediate sets

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

The minimum oracle circuit size problem ⋮ The power of natural properties as oracles ⋮ The final nail in the coffin of statistically-secure obfuscator ⋮ The Complexity of Complexity ⋮ CNF and DNF succinct graph encodings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions

This page was built for publication: The Minimum Oracle Circuit Size Problem.