For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly simpler than
the known reduction of Masek, which is from Circuit-SAT. We then present
a more complex, approximation-preserving reduction, that yields new
inapproximability results for Min-DNF. Finally, we extend known hardness
results for Min-TC0 to obtain new hardness results for Min-AC0, under
cryptographic assumptions.