Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table

DOI10.1137/060664537zbMath1165.68030MaRDI 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

zbMATH Keywords

approximation algorithms; complexity theory; machine learning theory; truth table minimization

Mathematics Subject Classification ID

68Q32: Computational learning theory

68T05: Learning and adaptive systems in artificial intelligence

03B05: Classical propositional logic

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

68W25: Approximation algorithms

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The non-hardness of approximating circuit size, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Compact DSOP and partial DSOP forms, Arithmetic circuits: the chasm at depth four gets wider, 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, Approximability of minimum AND-circuits, Mining circuit lower bound proofs for meta-algorithms, Uniform derandomization from pathetic lower bounds, The Complexity of Complexity, Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization