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

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

zbMATH Keywords

approximation algorithmscomplexity theorymachine learning theorytruth table minimization

Mathematics Subject Classification ID

Related Items (23)

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

This page was built for publication: Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table