[Lowerbounds, Upperbounds]

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.

When you use AUCTeX to compile a LaTeX document that contains an error, the compilation will fail and AUCTeX will remind you in the minibuffer area: LaTeX errors in `*foo output*'. Use C-c ` to display. By pressing C-c `, which invokes the next-error function, you can navigate to the source locations of the errors and fix them one by one. It surely is one of the most convenient features of AUCTeX.

But AUCTeX also has a lesser known feature in this regard: by pressing C-c C-w, which by default binds to TeX-toggle-debug-boxes, you can tell AUCTeX whether the debugger should consider underfull/overfull \hboxes as errors too. When preparing for the final(*) revision of a document, this feature really makes locating the bad \hboxes a breeze!

(What’s remaining are of course the \vboxes, but there doesn’t seem to be any good way to locate them using the output messages alone.)

(*) It is usually not a very productive idea to fix bad boxes before the document content is finalized.