ECCC-Report TR05-126https://eccc.weizmann.ac.il/report/2005/126Comments and Revisions published for TR05-126en-usSun, 25 Jul 2021 14:01:25 +0300
Comment 2
| LaTeX error makes the previous comment unreadable. |
Eric Allender
https://eccc.weizmann.ac.il/report/2005/126#comment2Trying 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.Sun, 25 Jul 2021 14:01:25 +0300https://eccc.weizmann.ac.il/report/2005/126#comment2
Comment 1
| Correction to the statement of Lemma 14 |
Eric Allender
https://eccc.weizmann.ac.il/report/2005/126#comment1Lemma 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.Sun, 25 Jul 2021 10:55:46 +0300https://eccc.weizmann.ac.il/report/2005/126#comment1
Paper TR05-126
| Minimizing DNF Formulas and AC0 Circuits Given a Truth Table |
Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Michael Saks
https://eccc.weizmann.ac.il/report/2005/126For 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.
Sat, 05 Nov 2005 02:20:21 +0200https://eccc.weizmann.ac.il/report/2005/126