Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with DNF minimization:
TR05-127 | 5th November 2005
Vitaly Feldman

Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries

Revisions: 1

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

TR09-107 | 28th October 2009
Kevin Dick, Chris Umans

Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

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

ISSN 1433-8092 | Imprint