Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
From MaRDI portal
Publication:3614150
DOI10.1137/060664537zbMath1165.68030OpenAlexW2056994701MaRDI QIDQ3614150
Paul McCabe, Toniann Pitassi, Eric W. Allender, Michael E. Saks, Lisa Hellerstein
Publication date: 16 March 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060664537
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Uniform derandomization from pathetic lower bounds, Compact DSOP and partial DSOP forms, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, The complexity of Boolean formula minimization, Partially unate Boolean functions: properties of their sum-of-products representations, The power of natural properties as oracles, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), The final nail in the coffin of statistically-secure obfuscator, Arithmetic circuits: the chasm at depth four gets wider, The Complexity of Complexity, Random arithmetic formulas can be reconstructed efficiently, Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, Unnamed Item, Unnamed Item, Unnamed Item, The non-hardness of approximating circuit size, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization, Unnamed Item, Unnamed Item, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Approximability of minimum AND-circuits, Circuit lower bounds from NP-hardness of MCSP under turing reductions, Mining circuit lower bound proofs for meta-algorithms
