SPEAKER: Karl Wimmer
TIME: Wednesday 12-1pm, May 23, 2007
PLACE: NSH 1507
TITLE: Approximation by DNF: Examples and Counterexamples
ABSTRACT:
Say that f : {0,1}^n -> {0,1} eps-approximates g : {0,1}^n -> {0,1} if the functions disagree on at most an \eps fraction of points. This talk will survey two results about approximation by DNF and other small-depth circuits:
(1) For every constant 0 < eps < 1/2 there is a DNF of size 2^{O(sqrt{n})} that \eps-approximates the Majority function on n bits, and this is optimal up to the constant in the exponent.
(2) There is a monotone function F : {0,1}^n -> {0,1} with total influence (AKA average sensitivity) I(F) <= O(log n) such that any DNF or CNF that .01-approximates F requires size 2^{Omega(n / log n)} and such that *any* unbounded fan-in AND-OR-NOT circuit that .01-approximates F requires size Omega(n / log n). This disproves a conjecture of Benjamini, Kalai, and Schramm (appearing in [BKS99,Kal00,KS05]).
This is joint work with Ryan O’Donnell.
