Circuit minimization problem

DOI10.1145/335305.335314zbMath1296.94182MaRDI QIDQ3191973

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

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The Evolution of Representation in Simple Cognitive Networks, Easiness assumptions and hardness tests: Trading time for zero error, The non-hardness of approximating circuit size, Random arithmetic formulas can be reconstructed efficiently, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, The complexity of Boolean formula minimization, The complexity of explicit constructions, Almost-natural proofs, Approximability of minimum AND-circuits, 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, Natural Proofs versus Derandomization, 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, Unnamed Item, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization