Harvard Theory of Computation Seminar
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries
Vitaly Feldman, Harvard University
Place and Time: Monday 2/6, Maxwell-Dworkin 319
Refreshments at 2:30, talk at 2:45.
ABSTRACT
Two-level logic minimization, or producing a small DNF
expression
consistent with a given complete truth table of a Boolean function
is a
classical problem in computer science formulated by Quine in 1952
(we denote
it by TT-MinDNF). It has been since one of the key problems in
logic design
and, more recently, found applications in a number of other areas.
In 1979
Masek showed that finding a DNF formula of the minimum size is an
NP-complete problem.
On the other hand, the best known polynomial approximation
algorithm is
based on a reduction to the SET-COVER problem and produces a DNF
formula of
size O(d \cdot OPT), where d is the number of variables. We prove
that
TT-MinDNF is NP-hard to approximate within d^\gamma for some
constant
\gamma>0, establishing the first inapproximability result for the
problem.
In this talk I will show two approximation-preserving
reductions to
TT-MinDNF. The first and the simpler one from hypergraph vertex
cover that
gives the above-mentioned inapproximability factor under a stronger
assumption (NP \notsubseteq DTIME(n^{\log{n}})). I will then show a
direct
reduction from a multi-prover proof system for NP that establishes
the
claimed result.
I will also show that inapproximability of TT-MinDNF implies
hardness
results for proper PAC learning of DNF expressions with
membership queries even when learning with respect to the uniform
distribution only.