All reports by Author Kevin Dick:

__
TR09-107
| 28th October 2009
__

Kevin Dick, Chris Umans#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

Kevin Dick, Chris Umans

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 >>>