### DIMACS Theoretical Computer Science Seminar

Title: Minimization of DNF Formulas Given a Truth Table

Speaker: **Lisa Hellerstein**, Polytechnic University

Date: March 21, 2006 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A classical problem in logic minimization is to find the smallest DNF formula
consistent with a given truth table. We call this problem minDNF. It is
well-known that minDNF is a special case of Set Cover, and that the standard
greedy set cover heuristic can be used to obtain an approximate solution to
minDNF that is within a factor O(n) of optimal, where n is the number of
variables on which the function is defined.

In the 1970's, Masek showed that minDNF is NP-complete. However, few people
have taken the time to understand his proof, which consists of a gadget-based
reduction from Circuit-SAT. We begin by presenting a new and simpler proof
that minDNF is NP-complete, by reduction from 3-Partite Set Cover. We then
show that unless NP is contained in quasipolynomial time, there is an
absolute constant $\delta < 1$ such that minDNF cannot be approximated to
within a factor $O(n^{\delta})$ of optimal.

We also construct an instance of minDNF on which the greedy set cover
heuristic produces a solution that is $Omega(n)$ larger than optimal.

The material in this talk is contained in a paper coauthored with Eric
Allender, Paul McCabe, Toni Pitassi, and Michael Saks.