Producing a small DNF expression consistent with given data is a
classical problem in computer science that occurs in a number of forms and
has numerous applications. We consider two standard variants of this
problem. The first one is two-level logic minimization or finding a minimal
more >>>

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are \Sigma_2^p-hard to approximate to within factors of n^{1/3-\epsilon} and n^{1/2-\epsilon} (where the previous results achieved n^{1/4 - \epsilon}), ... more >>>