Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-126 | 5th November 2005 00:00

#### Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

TR05-126
Authors: Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks
Publication: 5th November 2005 02:20
Keywords:

Abstract:

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly simpler than
the known reduction of Masek, which is from Circuit-SAT. We then present
a more complex, approximation-preserving reduction, that yields new
inapproximability results for Min-DNF. Finally, we extend known hardness
results for Min-TC0 to obtain new hardness results for Min-AC0, under
cryptographic assumptions.

### Comment(s):

Comment #1 to TR05-126 | 25th July 2021 10:55

#### Correction to the statement of Lemma 14

Authors: Eric Allender
Accepted on: 25th July 2021 10:55
Keywords:

Comment:

Lemma 14 states that there is a partition system with \$m = O(2^h h \log t)\$. However, if we make use of the construction given by Lemma 3.2 of [Lund, Yannakakis; JACM 1994] we actually obtain the bound \$m = O(2^{2h}t^2}\$.

The bound is used a few lines after Lemma 14, in giving a bound for the size of the entire universe: \$n^{O(k)} 2^{O(h)}\$. This bound still holds, using the corrected value in the statement of Lemma 14.

Comment #2 to TR05-126 | 25th July 2021 14:01

#### LaTeX error makes the previous comment unreadable.

Authors: Eric Allender
Accepted on: 25th July 2021 14:01
Keywords:

Comment:

Trying again. (ECCC doesn't have a "preview" option for comments.)

Lemma 14 states that there is a partition system with \$m=O(2^h h \log t)\$. However, if we make use of the construction given by Lemma 3.2 of [Lund, Yannakakis; JACM 1994] we actually obtain the bound \$m = O(2^{2h} t^2)\$.

The bound is used a few lines after Lemma 14, in giving a bound for the size of the entire universe: \$n^{O(k)} 2^{O(h)}\$. This bound still holds, using the corrected value in the statement of Lemma 14.

ISSN 1433-8092 | Imprint