The minimum oracle circuit size problem

DOI10.1007/S00037-016-0124-0MaRDI QIDQ2410683zbMATH OpenOpenAlexFDO

Authors Eric 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 complexityminimum circuit-size problemNP-intermediate setsPSPACE

Mathematics Subject Classification ID

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.
• Limits of minimum circuit size problem as oracle
• On the NP-Completeness of the Minimum Circuit Size Problem.
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity

Cites work

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

Cited in

(18)

• Circuit size relative to pseudorandom oracles
• Hardness of sparse sets and minimal circuit size problem
• Discrete logarithm and minimum circuit size
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• The Minimum Oracle Circuit Size Problem.
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Does looking inside a circuit help?
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Limits of minimum circuit size problem as oracle
• The non-hardness of approximating circuit size
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• SAT reduces to the minimum circuit size problem with a random oracle

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 Q2410683)