In the last post, I discussed the complexity of DNF minimization given a dataset. Specifically, given a dataset of input/output pairs, how hard is it to compute the smallest DNF consistent with ? In this post, we’ll look at a variant of this problem where one requires that the dataset specify a label for every point in .

DNF truth table minimization. DNF truth table minimization is the variant of DNF minimization where the input dataset is a truth table for a function . The extra constraint on the dataset can only make the problem easier, and indeed using the greedy approximation for Set-Cover, it is possible to approximate truth table minimization to within a factor of in polynomial-time. The first lower bound was proved by Masek in 1979 which showed that the exact variant is NP-hard. His result was never published though the proof was later reproduced and refined by Umans, Villa, and Sangiovanni-Vincentelli. Hardness of approximation remained open until 2006, when two independent papers came out which obtained hardness of approximating within a factor of .

It is NP-hard to approximate truth table DNF minimization within a factor of for some .

Feldman 2009

Allender, Hellerstein, McCabe, Pitassi, and Saks independently obtained the same hardness of approximation under the stronger assumption that . This was subsequently improved by Khot and Saket (2008) to an approximation factor of for all constants , also under the stronger assumption that .

The proofs of these results use PCP techniques and are significantly more involved than that of DNF minimization in the dataset setting. A key intermediate step is proving hardness for partial truth table minimization. In this variant, the input is still a truth table of size but some entries are starred indicating “don’t care” inputs. Hardness of approximating this variant follows from hardness of approximating the label cover problem. After establishing hardness, the partial truth table variant can be reduced to truth table minimization using ideas from Gimpel (1965).

Learning hardness. Given access to random labeled samples from some unknown DNF where is drawn from an unknown distribution D, how hard is it to find a hypothesis that approximates over D? This problem is known as PAC learning DNFs and is a fundamental problem in learning theory. In the influential paper introducing PAC learning, Valiant showed that DNFs with terms can be learned by width- CNFs in polynomial time when is a constant. On the flip side, Pitt and Valiant showed that learning size- DNFs by size- DNFs is NP-hard (this is a consequence of the NP-hardness discussed in the first blog post).

The landscape changes if the learner is allowed to assume that the distribution in the learning instance is uniform. The Pitt-Valiant NP-hardness result crucially relies on constructing a “pathological” distribution which makes the problem hard. In fact, with this new distributional assumption, it is possible to learn size- DNFs by size- DNFs:

There is an algorithm that learns size- DNFs with size- DNFs over the uniform distribution in time .

Verbeurgt 1990

Any algorithm that learns DNFs over the uniform distribution can also be used to solve DNF minimization given a truth table. This observation was made by Feldman. The basic idea is to provide the learner with uniform random samples labeled according to the truth table. Using this observation and the hardness result from Khot and Saket, one can obtain the following learning lower bound which complements the above upper bound.

The following holds for all constants . If , then size- DNFs cannot be learned by size- DNFs in polynomial time. This holds even if the distribution in the learning instance is uniform and the target is a -junta over variables.

In fact, the above theorem also holds even if the learner has access to membership queries. This means that in addition to random samples, the learner is allowed to query the function on arbitrary inputs (note Verbeurgt’s algorithm only uses random samples). We also remark that the above theorem requires the learner to output a hypothesis that has accuracy over the uniform distribution. This is a weakness of the hardness result. For example, it does not rule out PAC learning size- DNFs by size- DNFs to error over the uniform distribution. Regardless, it gives some evidence that Verbeurgt’s algorithm is unlikely to be significantly improved.

Conclusion and open problems. DNF minimization is a fundamental problem in computer science and has many connections to learning. We’ve seen that assumptions on the structure of the dataset can greatly affect the complexity of the problem, just as distributional assumptions in the learning setting can affect the complexity of the learning task. While a lot of progress has been made on understanding the nuances of these assumptions, there are still many directions to explore:

1. Gaps remain between the approximation lower bounds and the approximation upper bounds for these problems. For example, can one show hardness of approximating DNF minimization in the dataset setting to within a factor of ? Or perhaps it is possible to improve the trivial m-approximation upper bound?

2. Can Verbeurgt’s algorithm be improved to run in time ? The -approximation algorithm for truth table minimization runs in polynomial-time. A priori nothing rules out a -time algorithm for learning size- DNFs by size DNFs over the uniform distribution.

3. Is it hard to learn DNFs over the uniform distribution to constant error?

That’s it for this blog post! Thanks for reading!