Circuit minimization problem

DOI10.1145/335305.335314zbMath1296.94182OpenAlexW1966819396MaRDI QIDQ3191973

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

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

Related Items (47)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ 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 ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ The complexity of Boolean formula minimization ⋮ 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 Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Evolution of Representation in Simple Cognitive Networks ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ Optimising attractor computation in Boolean automata networks ⋮ Limits on the Computational Power of Random Strings ⋮ Arithmetic Expression Construction. ⋮ The complexity of explicit constructions ⋮ Almost-natural proofs ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Easiness assumptions and hardness tests: Trading time for zero error ⋮ The non-hardness of approximating circuit size ⋮ Natural Proofs versus Derandomization ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Investigations Concerning the Structure of Complete Sets ⋮ Approximability of minimum AND-circuits ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions ⋮ The hidden subgroup problem and MKTP ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

This page was built for publication: Circuit minimization problem