Circuit minimization problem

DOI10.1145/335305.335314MaRDI QIDQ3191973zbMATH OpenOpenAlexFDO

Authors Valentine Kabanets, Jin-Yi Cai

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335314

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the NP-Completeness of the Minimum Circuit Size Problem.
• On the (non) NP-hardness of computing circuit complexity
• Minimum \(\varepsilon\)-equivalent circuit size problem
• scientific article; zbMATH DE number 7250145
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity

Cited in

(76)

• Verifying minimum stable circuit values
• Approximability of minimum AND-circuits
• On approximability of Boolean formula minimization
• Minimum \(\varepsilon\)-equivalent circuit size problem
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Nonuniform reductions and NP-completeness
• Optimising attractor computation in Boolean automata networks
• The hidden subgroup problem and MKTP
• Mining circuit lower bound proofs for meta-algorithms
• Discrete logarithm and minimum circuit size
• Zero knowledge and circuit minimization
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• The minimum oracle circuit size problem
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Investigations concerning the structure of complete sets
• The Complexity of Complexity
• Limits on the Computational Power of Random Strings
• Minimum circuit size, graph isomorphism, and related problems
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• On nonadaptive reductions to the set of random strings and its dense subsets
• Nonuniform reductions and NP-completeness
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Circuit optimization by rewiring
• Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable
• Random arithmetic formulas can be reconstructed efficiently
• Minimum circuit size, graph isomorphism, and related problems
• Circuit lower bounds for MCSP from local pseudorandom generators
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• Hardness magnification near state-of-the-art lower bounds
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• Does looking inside a circuit help?
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• The evolution of representation in simple cognitive networks
• The non-hardness of approximating circuit size
• Progress in the solving of a circuit design problem
• Easiness assumptions and hardness tests: Trading time for zero error
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• Arithmetic Expression Construction.
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• The power of natural properties as oracles
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Paradigms for Unconditional Pseudorandom Generators
• The final nail in the coffin of statistically-secure obfuscator
• MCSP is hard for read-once nondeterministic branching programs
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The complexity of Boolean formula minimization
• Capturing one-way functions via NP-hardness of meta-complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Constructive separations and their consequences
• One-tape Turing machine and branching program lower bounds for MCSP
• A direct PRF construction from Kolmogorov complexity
• Constant depth formula and partial function versions of MCSP are hard
• On witness encryption and laconic zero-knowledge arguments
• Gap MCSP is not (Levin) NP-complete in obfustopia
• Search-to-decision reductions for Kolmogorov complexity
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• The non-uniform perebor conjecture for time-bounded Kolmogorov complexity is false
• On black-box meta complexity and function inversion
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• The complexity of explicit constructions
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Regularization of low error PCPs and an application to MCSP
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Lower bounds for Levin-Kolmogorov complexity
• Almost-natural proofs
• Symmetric exponential time requires near-maximum circuit size
• One-tape Turing machine and branching program lower bounds for MCSP
• A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
• Lifting for constant-depth circuits and applications to MCSP
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Circuit minimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191973)