Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Approximation by DNF: Examples and Counterexamples
verfasst von : Ryan O’Donnell, Karl Wimmer
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Say that
f
:{0,1}
n
→{0,1}
ε
-approximates
g
: {0,1}
n
→{0,1} if the functions disagree on at most an
ε
fraction of points. This paper contains two results about approximation by DNF and other small-depth circuits:
(1) For every constant 0 <
ε
< 1/2 there is a DNF of size
$2^{O(\sqrt{n})}$
that
ε
-approximates the Majority function on
n
bits, and this is optimal up to the constant in the exponent.
(2) There is a monotone function
$\mathcal{F} : \{{0,1}\}^{n} \rightarrow \{{0,1}\}$
with total influence (AKA average sensitivity)
${\mathbb{I}}({\mathcal{F}}) \leq O(\log n)$
such that any DNF or CNF that .01-approximates
${\mathcal{F}}$
requires size 2
Ω
(
n
/ log
n
)
and such that
any
unbounded fan-in AND-OR-NOT circuit that .01-approximates
${\mathcal{F}}$
requires size
Ω
(
n
/ log
n
). This disproves a conjecture of Benjamini, Kalai, and Schramm (appearing in [BKS99,Kal00,KS05]).