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

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