The minimum oracle circuit size problem

DOI10.1007/s00037-016-0124-0zbMath1408.68065OpenAlexW2402456376MaRDI QIDQ2410683

Eric W. Allender, Dhiraj Holden, Valentine Kabanets

Publication date: 18 October 2017

Published in: Computational Complexity (Search for Journal in Brave)

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

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)

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Does Looking Inside a Circuit Help

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The isomorphism conjecture for constant depth reductions
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The complexity of combinatorial problems with succinct input representation
• Rudimentary reductions revisited
• Gap-definable counting classes
• On the complexity of single-rule datalog queries.
• Time-space tradeoffs for satisfiability
• On relationships between statistical zero-knowledge proofs
• Zero Knowledge and Circuit Minimization
• The Minimum Oracle Circuit Size Problem.
• Circuit minimization problem
• Theory of Formal Systems. (AM-47)
• Succinct representations of graphs
• PP is as Hard as the Polynomial-Time Hierarchy
• Randomness conservation inequalities; information and independence in mathematical theories
• Separating Nondeterministic Time Complexity Classes
• Rudimentary Predicates and Relative Computation
• Complexity classes defined by counting quantifiers
• A note on succinct representations of graphs
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Extensional Uniformity for Boolean Circuits
• Power from Random Strings

This page was built for publication: The minimum oracle circuit size problem