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